library(tidyverse)
library(modelr)
library(rsample)
library(broom)
library(magrittr)

set.seed(1234)

theme_set(theme_minimal())

Resampling methods

Resampling methods are essential to test and evaluate statistical models. Because you likely do not have the resources or capabilities to repeatedly sample from your population of interest, instead you can repeatedly draw from your original sample to obtain additional information about your model. For instance, you could repeatedly draw samples from your data, estimate a linear regression model on each sample, and then examine how the estimated model differs across each sample. This allows you to assess the variability and stability of your model in a way not possible if you can only fit the model once.

Validation set

One issue with using the same data to both fit and evaluate our model is that we will bias our model towards fitting the data that we have. We may fit our function to create the results we expect or desire, rather than the “true” function. Instead, we can split our data into distinct training and validation sets. The training set can be used repeatedly to explore or train different models. Once we have a stable model, we can apply it to the validation set of held-out data to determine (unbiasedly) whether the model makes accurate predictions.

Regression

Here we will examine the relationship between horsepower and car mileage in the Auto dataset (found in library(ISLR)):

library(ISLR)

Auto <- as_tibble(Auto)
Auto
## # A tibble: 392 x 9
##      mpg cylinders displacement horsepower weight acceleration  year origin
##  * <dbl>     <dbl>        <dbl>      <dbl>  <dbl>        <dbl> <dbl>  <dbl>
##  1    18         8          307        130   3504         12      70      1
##  2    15         8          350        165   3693         11.5    70      1
##  3    18         8          318        150   3436         11      70      1
##  4    16         8          304        150   3433         12      70      1
##  5    17         8          302        140   3449         10.5    70      1
##  6    15         8          429        198   4341         10      70      1
##  7    14         8          454        220   4354          9      70      1
##  8    14         8          440        215   4312          8.5    70      1
##  9    14         8          455        225   4425         10      70      1
## 10    15         8          390        190   3850          8.5    70      1
## # ... with 382 more rows, and 1 more variable: name <fct>
ggplot(Auto, aes(horsepower, mpg)) +
  geom_point()

The relationship does not appear to be strictly linear:

ggplot(Auto, aes(horsepower, mpg)) +
  geom_point() +
  geom_smooth(method = "lm", se = FALSE)

Perhaps by adding quadratic terms to the linear regression we could improve overall model fit. To evaluate the model, we will split the data into a training set and validation set, estimate a series of higher-order models, and calculate a test statistic summarizing the accuracy of the estimated mpg. To calculate the accuracy of the model, we will use Mean Squared Error (MSE), defined as

\[MSE = \frac{1}{n} \sum_{i = 1}^{n}{(y_i - \hat{f}(x_i))^2}\]

where:

  • \(y_i =\) the observed response value for the \(i\)th observation
  • \(\hat{f}(x_i) =\) the predicted response value for the \(i\)th observation given by \(\hat{f}\)
  • \(n =\) the total number of observations

Boo math! Actually this is pretty intuitive. All we’re doing is for each observation, calculating the difference between the actual and predicted values for \(y\), squaring that difference, then calculating the average across all observations. An MSE of 0 indicates the model perfectly predicted each observation. The larger the MSE, the more error in the model.

For this task, first we use rsample::initial_split() to create training and validation sets (using a 50/50 split), then estimate a linear regression model without any quadratic terms.

  • I use set.seed() in the beginning - whenever you are writing a script that involves randomization (here, random subsetting of the data), always set the seed at the beginning of the script. This ensures the results can be reproduced precisely.1
  • I also use the glm() function rather than lm() - if you don’t change the family parameter, the results of lm() and glm() are exactly the same.2
set.seed(1234)

auto_split <- initial_split(data = Auto, prop = 0.5)
auto_train <- training(auto_split)
auto_test <- testing(auto_split)
auto_lm <- glm(mpg ~ horsepower, data = auto_train)
summary(auto_lm)
## 
## Call:
## glm(formula = mpg ~ horsepower, data = auto_train)
## 
## Deviance Residuals: 
##      Min        1Q    Median        3Q       Max  
## -13.7105   -3.4442   -0.5342    2.6256   15.1015  
## 
## Coefficients:
##              Estimate Std. Error t value Pr(>|t|)    
## (Intercept) 40.057910   1.054798   37.98   <2e-16 ***
## horsepower  -0.157604   0.009402  -16.76   <2e-16 ***
## ---
## Signif. codes:  0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1
## 
## (Dispersion parameter for gaussian family taken to be 24.80151)
## 
##     Null deviance: 11780.6  on 195  degrees of freedom
## Residual deviance:  4811.5  on 194  degrees of freedom
## AIC: 1189.6
## 
## Number of Fisher Scoring iterations: 2

To estimate the MSE for a single partition (i.e. for a training or validation set):

  1. Use broom::augment() to generate predicted values for the data set
  2. Calculate the residuals and square each value
  3. Calculate the mean of all the squared residuals in the data set

For the training set, this would look like:

(train_mse <- augment(auto_lm, newdata = auto_train) %>%
  mutate(.resid = mpg - .fitted,
         .resid2 = .resid ^ 2) %$%
  mean(.resid2))
## [1] 24.54843

Note the special use of the $%$ pipe operator from the magrittr package. This allows us to directly access columns from the data frame entering the pipe. This is especially useful for integrating non-tidy functions into a tidy operation.

For the validation set:

(test_mse <- augment(auto_lm, newdata = auto_test) %>%
  mutate(.resid = mpg - .fitted,
         .resid2 = .resid ^ 2) %$%
  mean(.resid2))
## [1] 23.38243

For a strictly linear model, the MSE for the validation set is 23.38. How does this compare to a quadratic model? We can use the poly() function in conjunction with a map() iteration to estimate the MSE for a series of models with higher-order polynomial terms:

# visualize each model
ggplot(Auto, aes(horsepower, mpg)) +
  geom_point(alpha = .1) +
  geom_smooth(aes(color = "1"),
              method = "glm",
              formula = y ~ poly(x, i = 1),
              se = FALSE) +
  geom_smooth(aes(color = "2"),
              method = "glm",
              formula = y ~ poly(x, i = 2),
              se = FALSE) +
  geom_smooth(aes(color = "3"),
              method = "glm",
              formula = y ~ poly(x, i = 3),
              se = FALSE) +
  geom_smooth(aes(color = "4"),
              method = "glm",
              formula = y ~ poly(x, i = 4),
              se = FALSE) +
  geom_smooth(aes(color = "5"),
              method = "glm",
              formula = y ~ poly(x, i = 5),
              se = FALSE) +
  scale_color_brewer(type = "qual", palette = "Dark2") +
  labs(x = "Horsepower",
       y = "MPG",
       color = "Highest-order\npolynomial")

# function to estimate model using training set and generate fit statistics
# using the test set
poly_results <- function(train, test, i) {
  # Fit the model to the training set
  mod <- glm(mpg ~ poly(horsepower, i), data = train)
  
  # `augment` will save the predictions with the test data set
  res <- augment(mod, newdata = test) %>%
    # calculate residuals for future use
    mutate(.resid = mpg - .fitted)
  
  # Return the test data set with the additional columns
  res
}

# function to return MSE for a specific higher-order polynomial term
poly_mse <- function(i, train, test){
  poly_results(train, test, i) %$%
    mean(.resid ^ 2)
}

cv_mse <- data_frame(terms = seq(from = 1, to = 5),
                     mse_test = map_dbl(terms, poly_mse, auto_train, auto_test))

ggplot(cv_mse, aes(terms, mse_test)) +
  geom_line() +
  labs(title = "Comparing quadratic linear models",
       subtitle = "Using validation set",
       x = "Highest-order polynomial",
       y = "Mean Squared Error")

Based on the MSE for the validation set, a polynomial model with a quadratic term (\(\text{horsepower}^2\)) produces the lowest average error. Adding cubic or higher-order terms is just not necessary.

Classification

Recall our efforts to predict passenger survival during the sinking of the Titanic.

library(titanic)
titanic <- as_tibble(titanic_train)

titanic %>%
  head() %>%
  knitr::kable()
PassengerId Survived Pclass Name Sex Age SibSp Parch Ticket Fare Cabin Embarked
1 0 3 Braund, Mr. Owen Harris male 22 1 0 A/5 21171 7.2500 S
2 1 1 Cumings, Mrs. John Bradley (Florence Briggs Thayer) female 38 1 0 PC 17599 71.2833 C85 C
3 1 3 Heikkinen, Miss. Laina female 26 0 0 STON/O2. 3101282 7.9250 S
4 1 1 Futrelle, Mrs. Jacques Heath (Lily May Peel) female 35 1 0 113803 53.1000 C123 S
5 0 3 Allen, Mr. William Henry male 35 0 0 373450 8.0500 S
6 0 3 Moran, Mr. James male NA 0 0 330877 8.4583 Q
survive_age_woman_x <- glm(Survived ~ Age * Sex, data = titanic,
                           family = binomial)
summary(survive_age_woman_x)
## 
## Call:
## glm(formula = Survived ~ Age * Sex, family = binomial, data = titanic)
## 
## Deviance Residuals: 
##     Min       1Q   Median       3Q      Max  
## -1.9401  -0.7136  -0.5883   0.7626   2.2455  
## 
## Coefficients:
##             Estimate Std. Error z value Pr(>|z|)   
## (Intercept)  0.59380    0.31032   1.913  0.05569 . 
## Age          0.01970    0.01057   1.863  0.06240 . 
## Sexmale     -1.31775    0.40842  -3.226  0.00125 **
## Age:Sexmale -0.04112    0.01355  -3.034  0.00241 **
## ---
## Signif. codes:  0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1
## 
## (Dispersion parameter for binomial family taken to be 1)
## 
##     Null deviance: 964.52  on 713  degrees of freedom
## Residual deviance: 740.40  on 710  degrees of freedom
##   (177 observations deleted due to missingness)
## AIC: 748.4
## 
## Number of Fisher Scoring iterations: 4

We can use the same validation set approach to evaluate the model’s accuracy. For classification models, instead of using MSE we examine the test error rate. That is, of all the predictions generated for the test set, what percentage of predictions are incorrect? The goal is to minimize this value as much as possible (ideally, until we make no errors and our error rate is \(0%\)).

# function to convert log-odds to probabilities
logit2prob <- function(x){
  exp(x) / (1 + exp(x))
}
# split the data into training and validation sets
titanic_split <- initial_split(data = titanic, prop = 0.5)

# fit model to training data
train_model <- glm(Survived ~ Age * Sex, data = training(titanic_split),
                   family = binomial)
summary(train_model)
## 
## Call:
## glm(formula = Survived ~ Age * Sex, family = binomial, data = training(titanic_split))
## 
## Deviance Residuals: 
##     Min       1Q   Median       3Q      Max  
## -2.1511  -0.7346  -0.5386   0.7339   2.2216  
## 
## Coefficients:
##             Estimate Std. Error z value Pr(>|z|)    
## (Intercept)  0.17464    0.41877   0.417 0.676659    
## Age          0.03570    0.01525   2.342 0.019198 *  
## Sexmale     -0.59608    0.56604  -1.053 0.292313    
## Age:Sexmale -0.06833    0.01994  -3.426 0.000612 ***
## ---
## Signif. codes:  0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1
## 
## (Dispersion parameter for binomial family taken to be 1)
## 
##     Null deviance: 478.37  on 353  degrees of freedom
## Residual deviance: 361.88  on 350  degrees of freedom
##   (92 observations deleted due to missingness)
## AIC: 369.88
## 
## Number of Fisher Scoring iterations: 4
# calculate predictions using validation set
x_test_accuracy <- augment(train_model, newdata = testing(titanic_split)) %>% 
  as_tibble() %>%
  mutate(pred = logit2prob(.fitted),
         pred = as.numeric(pred > .5))

# calculate test error rate
mean(x_test_accuracy$Survived != x_test_accuracy$pred, na.rm = TRUE)
## [1] 0.2166667

This interactive model generates an error rate of 21.7%. We could compare this error rate to alternative classification models, either other logistic regression models (using different formulas) or a tree-based method.

Drawbacks to validation sets

There are two main problems with validation sets:

  1. Validation estimates of the test error rates can be highly variable depending on which observations are sampled into the training and test sets. See what happens if we repeat the sampling, estimation, and validation procedure for the Auto data set:

    mse_variable <- function(Auto){
      auto_split <- initial_split(Auto, prop = 0.5)
      auto_train <- training(auto_split)
      auto_test <- testing(auto_split)
    
      cv_mse <- data_frame(terms = seq(from = 1, to = 5),
                           mse_test = map_dbl(terms, poly_mse, auto_train, auto_test))
    
      return(cv_mse)
    }
    
    rerun(10, mse_variable(Auto)) %>%
      bind_rows(.id = "id") %>%
      ggplot(aes(terms, mse_test, color = id)) +
      geom_line() +
      labs(title = "Variability of MSE estimates",
           subtitle = "Using the validation set approach",
           x = "Degree of Polynomial",
           y = "Mean Squared Error") +
      theme(legend.position = "none")

    Depending on the specific training/test split, our MSE varies by up to 5.

  2. If you don’t have a large data set, you’ll have to dramatically shrink the size of your training set. Most statistical learning methods perform better with more observations - if you don’t have enough data in the training set, you might overestimate the error rate in the test set.

Leave-one-out cross-validation

An alternative method is leave-one-out cross validation (LOOCV). Like with the validation set approach, you split the data into two parts. However the difference is that you only remove one observation for the test set, and keep all remaining observations in the training set. The statistical learning method is fit on the \(n-1\) training set. You then use the held-out observation to calculate the \(MSE = (y_1 - \hat{y}_1)^2\) which should be an unbiased estimator of the test error. Because this MSE is highly dependent on which observation is held out, we repeat this process for every single observation in the data set. Mathematically, this looks like:

\[CV_{(n)} = \frac{1}{n} \sum_{i = 1}^{n}{MSE_i}\]

This method produces estimates of the error rate that have minimal bias and are relatively steady (i.e. non-varying), unlike the validation set approach where the MSE estimate is highly dependent on the sampling process for training/test sets. LOOCV is also highly flexible and works with any kind of predictive modeling.

Of course the downside is that this method is computationally difficult. You have to estimate \(n\) different models - if you have a large \(n\) or each individual model takes a long time to compute, you may be stuck waiting a long time for the computer to finish its calculations.

LOOCV in linear regression

We can use the loo_cv() function in the rsample library to compute the LOOCV of any linear or logistic regression model. It takes a single argument: the data frame being cross-validated. For the Auto dataset, this looks like:

loocv_data <- loo_cv(Auto)
loocv_data
## # Leave-one-out cross-validation 
## # A tibble: 392 x 2
##    splits       id        
##    <list>       <chr>     
##  1 <S3: rsplit> Resample1 
##  2 <S3: rsplit> Resample2 
##  3 <S3: rsplit> Resample3 
##  4 <S3: rsplit> Resample4 
##  5 <S3: rsplit> Resample5 
##  6 <S3: rsplit> Resample6 
##  7 <S3: rsplit> Resample7 
##  8 <S3: rsplit> Resample8 
##  9 <S3: rsplit> Resample9 
## 10 <S3: rsplit> Resample10
## # ... with 382 more rows

Each element of loocv_data$splits is an object of class rsplit. This is essentially an efficient container for storing both the analysis data (i.e. the training data set) and the assessment data (i.e. the validation data set). If we print the contents of a single rsplit object:

first_resample <- loocv_data$splits[[1]]
first_resample
## <391/1/392>

This tells us there are 391 observations in the analysis set, 1 observation in the assessment set, and the original data set contained 392 observations. To extract the analysis/assessment sets, use analysis() or assessment() respectively:

training(first_resample)
## # A tibble: 391 x 9
##      mpg cylinders displacement horsepower weight acceleration  year origin
##    <dbl>     <dbl>        <dbl>      <dbl>  <dbl>        <dbl> <dbl>  <dbl>
##  1    18         8          307        130   3504         12      70      1
##  2    15         8          350        165   3693         11.5    70      1
##  3    18         8          318        150   3436         11      70      1
##  4    16         8          304        150   3433         12      70      1
##  5    17         8          302        140   3449         10.5    70      1
##  6    15         8          429        198   4341         10      70      1
##  7    14         8          454        220   4354          9      70      1
##  8    14         8          440        215   4312          8.5    70      1
##  9    14         8          455        225   4425         10      70      1
## 10    15         8          390        190   3850          8.5    70      1
## # ... with 381 more rows, and 1 more variable: name <fct>
assessment(first_resample)
## # A tibble: 1 x 9
##     mpg cylinders displacement horsepower weight acceleration  year origin
##   <dbl>     <dbl>        <dbl>      <dbl>  <dbl>        <dbl> <dbl>  <dbl>
## 1    25         4          113         95   2228           14    71      3
## # ... with 1 more variable: name <fct>

Given this new loocv_data data frame, we write a function that will, for each resample:

  1. Obtain the analysis data set (i.e. the \(n-1\) training set)
  2. Fit a linear regression model
  3. Predict the test data (also known as the assessment data, the \(1\) test set) using the broom package
  4. Determine the MSE for each sample
holdout_results <- function(splits) {
  # Fit the model to the n-1
  mod <- glm(mpg ~ horsepower, data = analysis(splits))
  
  # Save the heldout observation
  holdout <- assessment(splits)
  
  # `augment` will save the predictions with the holdout data set
  res <- augment(mod, newdata = holdout) %>%
    # calculate residuals for future use
    mutate(.resid = mpg - .fitted)
  
  # Return the assessment data set with the additional columns
  res
}

This function works for a single resample:

holdout_results(loocv_data$splits[[1]])
## # A tibble: 1 x 12
##     mpg cylinders displacement horsepower weight acceleration  year origin
##   <dbl>     <dbl>        <dbl>      <dbl>  <dbl>        <dbl> <dbl>  <dbl>
## 1    25         4          113         95   2228           14    71      3
## # ... with 4 more variables: name <fct>, .fitted <dbl>, .se.fit <dbl>,
## #   .resid <dbl>

To compute the MSE for each heldout observation (i.e. estimate the test MSE for each of the \(n\) observations), we use the map() function from the purrr package to estimate the model for each training test, then calculate the MSE for each observation in each test set:

loocv_data$results <- map(loocv_data$splits, holdout_results)
loocv_data$mse <- map_dbl(loocv_data$results, ~ mean(.$.resid ^ 2))
loocv_data
## # Leave-one-out cross-validation 
## # A tibble: 392 x 4
##    splits       id         results                mse
##    <list>       <chr>      <list>               <dbl>
##  1 <S3: rsplit> Resample1  <tibble [1 × 12]>  0.00355
##  2 <S3: rsplit> Resample2  <tibble [1 × 12]>  1.25   
##  3 <S3: rsplit> Resample3  <tibble [1 × 12]> 19.6    
##  4 <S3: rsplit> Resample4  <tibble [1 × 12]>  2.42   
##  5 <S3: rsplit> Resample5  <tibble [1 × 12]> 16.7    
##  6 <S3: rsplit> Resample6  <tibble [1 × 12]> 97.0    
##  7 <S3: rsplit> Resample7  <tibble [1 × 12]> 57.7    
##  8 <S3: rsplit> Resample8  <tibble [1 × 12]>  1.77   
##  9 <S3: rsplit> Resample9  <tibble [1 × 12]> 15.3    
## 10 <S3: rsplit> Resample10 <tibble [1 × 12]> 24.2    
## # ... with 382 more rows

Now we can compute the overall LOOCV MSE for the data set by calculating the mean of the mse column:

loocv_data %>%
  summarize(mse = mean(mse))
## # Leave-one-out cross-validation 
## # A tibble: 1 x 1
##     mse
##   <dbl>
## 1  24.2

We can also use this method to compare the optimal number of polynomial terms as before.

# modified function to estimate model with varying highest order polynomial
holdout_results <- function(splits, i) {
  # Fit the model to the n-1
  mod <- glm(mpg ~ poly(horsepower, i), data = analysis(splits))
  
  # Save the heldout observation
  holdout <- assessment(splits)
  
  # `augment` will save the predictions with the holdout data set
  res <- augment(mod, newdata = holdout) %>%
    # calculate residuals for future use
    mutate(.resid = mpg - .fitted)
  
  # Return the assessment data set with the additional columns
  res
}

# function to return MSE for a specific higher-order polynomial term
poly_mse <- function(i, loocv_data){
  loocv_mod <- loocv_data %>%
    mutate(results = map(splits, holdout_results, i),
           mse = map_dbl(results, ~ mean(.$.resid ^ 2)))
  
  mean(loocv_mod$mse)
}

cv_mse <- data_frame(terms = seq(from = 1, to = 5),
                     mse_loocv = map_dbl(terms, poly_mse, loocv_data))
cv_mse
## # A tibble: 5 x 2
##   terms mse_loocv
##   <int>     <dbl>
## 1     1      24.2
## 2     2      19.2
## 3     3      19.3
## 4     4      19.4
## 5     5      19.0
ggplot(cv_mse, aes(terms, mse_loocv)) +
  geom_line() +
  labs(title = "Comparing quadratic linear models",
       subtitle = "Using LOOCV",
       x = "Highest-order polynomial",
       y = "Mean Squared Error")

And arrive at a similar conclusion. There may be a very marginal advantage to adding a fifth-order polynomial, but not substantial enough for the additional complexity over a mere second-order polynomial.

LOOCV in classification

Let’s verify the error rate of our interactive terms model for the Titanic data set:

# function to generate assessment statistics for titanic model
holdout_results <- function(splits) {
  # Fit the model to the n-1
  mod <- glm(Survived ~ Age * Sex, data = analysis(splits),
             family = binomial)
  
  # Save the heldout observation
  holdout <- assessment(splits)
  
  # `augment` will save the predictions with the holdout data set
  res <- augment(mod, newdata = assessment(splits)) %>% 
    as_tibble() %>%
    mutate(pred = logit2prob(.fitted),
           pred = as.numeric(pred > .5))

  # Return the assessment data set with the additional columns
  res
}

titanic_loocv <- loo_cv(titanic) %>%
  mutate(results = map(splits, holdout_results),
         error_rate = map_dbl(results, ~ mean(.$Survived != .$pred, na.rm = TRUE)))
mean(titanic_loocv$error_rate, na.rm = TRUE)
## [1] 0.219888

In a classification problem, the LOOCV tells us the average error rate based on our predictions. So here, it tells us that the interactive Age * Sex model has a 22% error rate. This is similar to the validation set result (\(21.7\%\))

Exercise: LOOCV in linear regression

  1. Estimate the LOOCV MSE of a linear regression of the relationship between admission rate and cost in the scorecard dataset.

    Click for the solution

    library(rcfss)
    
    # function to estimate heldout results for model
    holdout_results <- function(splits) {
      # Fit the model to the n-1
      mod <- glm(cost ~ admrate, data = analysis(splits))
    
      # Save the heldout observation
      holdout <- assessment(splits)
    
      # `augment` will save the predictions with the holdout data set
      res <- augment(mod, newdata = holdout) %>%
        # calculate residuals for future use
        mutate(.resid = cost - .fitted)
    
      # Return the assessment data set with the additional columns
      res
    }
    
    scorecard_loocv <- loo_cv(scorecard) %>%
      mutate(results = map(splits, holdout_results),
             mse = map_dbl(results, ~ mean(.$.resid ^ 2)))
    mean(scorecard_loocv$mse, na.rm = TRUE)
    ## [1] 147752431

  2. Estimate the LOOCV MSE of a logistic regression model of voter turnout using only mhealth as the predictor. Compare this to the LOOCV MSE of a logistic regression model using all available predictors. Which is the better model?

    Click for the solution

    Because this problem requires two separate regression formulas, rather than writing holdout_results() twice I create a second argument formula to the function. as.formula() stores a formula for a function as a separate object and can be passed directly into glm().

    # function to generate assessment statistics for titanic model
    # add the formula argument to pass the regression formula
    holdout_results <- function(splits, formula) {
      # Fit the model to the n-1
      mod <- glm(formula, data = analysis(splits),
                 family = binomial)
    
      # Save the heldout observation
      holdout <- assessment(splits)
    
      # `augment` will save the predictions with the holdout data set
      res <- augment(mod, newdata = assessment(splits)) %>% 
        as_tibble() %>%
        mutate(pred = logit2prob(.fitted),
               pred = as.numeric(pred > .5))
    
      # Return the assessment data set with the additional columns
      res
    }
    
    # basic model
    mh_loocv_lite <- loo_cv(mental_health) %>%
      mutate(results = map(splits, holdout_results,
                           formula = as.formula(vote96 ~ mhealth)),
             error_rate = map_dbl(results, ~ mean(.$vote96 != .$pred, na.rm = TRUE)))
    mean(mh_loocv_lite$error_rate, na.rm = TRUE)
    ## [1] 0.317388
    # full model
    mh_loocv_full <- loo_cv(mental_health) %>%
      mutate(results = map(splits, holdout_results,
                           formula = as.formula(vote96 ~ .)),
             error_rate = map_dbl(results, ~ mean(.$vote96 != .$pred, na.rm = TRUE)))
    mean(mh_loocv_full$error_rate, na.rm = TRUE)
    ## [1] 0.2817008

    The full model is better and has a lower error rate.

k-fold cross-validation

A less computationally-intensive approach to cross validation is \(k\)-fold cross-validation. Rather than dividing the data into \(n\) groups, one divides the observations into \(k\) groups, or folds, of approximately equal size. The first fold is treated as the validation set, and the model is estimated on the remaining \(k-1\) folds. This process is repeated \(k\) times, with each fold serving as the validation set precisely once. The \(k\)-fold CV estimate is calculated by averaging the MSE values for each fold:

\[CV_{(k)} = \frac{1}{k} \sum_{i = 1}^{k}{MSE_i}\]

As you may have noticed, LOOCV is a special case of \(k\)-fold cross-validation where \(k = n\). More typically researchers will use \(k=5\) or \(k=10\) depending on the size of the data set and the complexity of the statistical model.

k-fold CV in linear regression

Let’s go back to the Auto data set. Instead of LOOCV, let’s use 10-fold CV to compare the different polynomial models.

# modified function to estimate model with varying highest order polynomial
holdout_results <- function(splits, i) {
  # Fit the model to the training set
  mod <- glm(mpg ~ poly(horsepower, i), data = analysis(splits))
  
  # Save the heldout observations
  holdout <- assessment(splits)
  
  # `augment` will save the predictions with the holdout data set
  res <- augment(mod, newdata = holdout) %>%
    # calculate residuals for future use
    mutate(.resid = mpg - .fitted)
  
  # Return the assessment data set with the additional columns
  res
}

# function to return MSE for a specific higher-order polynomial term
poly_mse <- function(i, vfold_data){
  vfold_mod <- vfold_data %>%
    mutate(results = map(splits, holdout_results, i),
           mse = map_dbl(results, ~ mean(.$.resid ^ 2)))
  
  mean(vfold_mod$mse)
}

# split Auto into 10 folds
auto_cv10 <- vfold_cv(data = Auto, v = 10)

cv_mse <- data_frame(terms = seq(from = 1, to = 5),
                     mse_vfold = map_dbl(terms, poly_mse, auto_cv10))
cv_mse
## # A tibble: 5 x 2
##   terms mse_vfold
##   <int>     <dbl>
## 1     1      24.1
## 2     2      19.2
## 3     3      19.3
## 4     4      19.4
## 5     5      18.9

How do these results compare to the LOOCV values?

auto_loocv <- loo_cv(Auto)

data_frame(terms = seq(from = 1, to = 5),
           `10-fold` = map_dbl(terms, poly_mse, auto_cv10),
           LOOCV = map_dbl(terms, poly_mse, auto_loocv)
) %>%
  gather(method, MSE, -terms) %>%
  ggplot(aes(terms, MSE, color = method)) +
  geom_line() +
  labs(title = "MSE estimates",
       x = "Degree of Polynomial",
       y = "Mean Squared Error",
       color = "CV Method")

Pretty much the same results.

Computational speed of LOOCV vs. \(k\)-fold CV

LOOCV

library(profvis)

profvis({
  data_frame(terms = seq(from = 1, to = 5),
             mse_vfold = map_dbl(terms, poly_mse, auto_loocv))
})

10-fold CV

profvis({
  data_frame(terms = seq(from = 1, to = 5),
             mse_vfold = map_dbl(terms, poly_mse, auto_cv10))
})

On my machine, 10-fold CV was about 40 times faster than LOOCV. Again, estimating \(k=10\) models is going to be much easier than estimating \(k=392\) models.

k-fold CV in logistic regression

You’ve gotten the idea by now, but let’s do it one more time on our interactive Titanic model.

# function to generate assessment statistics for titanic model
holdout_results <- function(splits) {
  # Fit the model to the training set
  mod <- glm(Survived ~ Age * Sex, data = analysis(splits),
             family = binomial)
  
  # Save the heldout observations
  holdout <- assessment(splits)
  
  # `augment` will save the predictions with the holdout data set
  res <- augment(mod, newdata = assessment(splits)) %>% 
    as_tibble() %>%
    mutate(pred = logit2prob(.fitted),
           pred = as.numeric(pred > .5))

  # Return the assessment data set with the additional columns
  res
}

titanic_cv10 <- vfold_cv(data = titanic, v = 10) %>%
  mutate(results = map(splits, holdout_results),
         error_rate = map_dbl(results, ~ mean(.$Survived != .$pred, na.rm = TRUE)))
mean(titanic_cv10$error_rate, na.rm = TRUE)
## [1] 0.2191913

Not a large difference from the LOOCV approach, but it take much less time to compute.

Exercise: k-fold CV

  1. Estimate the 10-fold CV MSE of a linear regression of the relationship between admission rate and cost in the scorecard dataset.

    Click for the solution

    # function to estimate heldout results for model
    holdout_results <- function(splits) {
      # Fit the model to the training set
      mod <- glm(cost ~ admrate, data = analysis(splits))
    
      # Save the heldout observations
      holdout <- assessment(splits)
    
      # `augment` will save the predictions with the holdout data set
      res <- augment(mod, newdata = holdout) %>%
        # calculate residuals for future use
        mutate(.resid = cost - .fitted)
    
      # Return the assessment data set with the additional columns
      res
    }
    
    scorecard_cv10 <- vfold_cv(data = scorecard, v = 10) %>%
      mutate(results = map(splits, holdout_results),
             mse = map_dbl(results, ~ mean(.$.resid ^ 2)))
    mean(scorecard_cv10$mse, na.rm = TRUE)
    ## [1] 143299151

  2. Estimate the 10-fold CV MSE of a logistic regression model of voter turnout using only mhealth as the predictor. Compare this to the LOOCV MSE of a logistic regression model using all available predictors. Which is the better model?

    Click for the solution

    # function to generate assessment statistics for titanic model
    # add the formula argument to pass the regression formula
    holdout_results <- function(splits, formula) {
      # Fit the model to the training set
      mod <- glm(formula, data = analysis(splits),
                 family = binomial)
    
      # Save the heldout observations
      holdout <- assessment(splits)
    
      # `augment` will save the predictions with the holdout data set
      res <- augment(mod, newdata = assessment(splits)) %>% 
        as_tibble() %>%
        mutate(pred = logit2prob(.fitted),
               pred = as.numeric(pred > .5))
    
      # Return the assessment data set with the additional columns
      res
    }
    
    # basic model
    mh_cv10_lite <- vfold_cv(data = mental_health, v = 10) %>%
      mutate(results = map(splits, holdout_results,
                           formula = as.formula(vote96 ~ mhealth)),
             error_rate = map_dbl(results, ~ mean(.$vote96 != .$pred, na.rm = TRUE)))
    mean(mh_cv10_lite$error_rate, na.rm = TRUE)
    ## [1] 0.3227099
    # full model
    mh_cv10_full <- vfold_cv(data = mental_health, v = 10) %>%
      mutate(results = map(splits, holdout_results,
                           formula = as.formula(vote96 ~ .)),
             error_rate = map_dbl(results, ~ mean(.$vote96 != .$pred, na.rm = TRUE)))
    mean(mh_cv10_full$error_rate, na.rm = TRUE)
    ## [1] 0.27873

Session Info

devtools::session_info()
##  setting  value                       
##  version  R version 3.5.1 (2018-07-02)
##  system   x86_64, darwin15.6.0        
##  ui       X11                         
##  language (EN)                        
##  collate  en_US.UTF-8                 
##  tz       America/Chicago             
##  date     2019-01-02                  
## 
##  package    * version    date       source        
##  abind        1.4-5      2016-07-21 CRAN (R 3.5.0)
##  assertthat   0.2.0      2017-04-11 CRAN (R 3.5.0)
##  backports    1.1.2      2017-12-13 CRAN (R 3.5.0)
##  base       * 3.5.1      2018-07-05 local         
##  base64enc    0.1-3      2015-07-28 CRAN (R 3.5.0)
##  bindr        0.1.1      2018-03-13 CRAN (R 3.5.0)
##  bindrcpp     0.2.2      2018-03-29 CRAN (R 3.5.0)
##  broom      * 0.5.0      2018-07-17 CRAN (R 3.5.0)
##  cellranger   1.1.0      2016-07-27 CRAN (R 3.5.0)
##  class        7.3-14     2015-08-30 CRAN (R 3.5.1)
##  cli          1.0.0      2017-11-05 CRAN (R 3.5.0)
##  colorspace   1.3-2      2016-12-14 CRAN (R 3.5.0)
##  compiler     3.5.1      2018-07-05 local         
##  crayon       1.3.4      2017-09-16 CRAN (R 3.5.0)
##  CVST         0.2-2      2018-05-26 CRAN (R 3.5.0)
##  datasets   * 3.5.1      2018-07-05 local         
##  ddalpha      1.3.4      2018-06-23 CRAN (R 3.5.0)
##  DEoptimR     1.0-8      2016-11-19 CRAN (R 3.5.0)
##  devtools     1.13.6     2018-06-27 CRAN (R 3.5.0)
##  digest       0.6.18     2018-10-10 cran (@0.6.18)
##  dimRed       0.1.0      2017-05-04 CRAN (R 3.5.0)
##  dplyr      * 0.7.8      2018-11-10 cran (@0.7.8) 
##  DRR          0.0.3      2018-01-06 CRAN (R 3.5.0)
##  evaluate     0.11       2018-07-17 CRAN (R 3.5.0)
##  forcats    * 0.3.0      2018-02-19 CRAN (R 3.5.0)
##  geometry     0.3-6      2015-09-09 CRAN (R 3.5.0)
##  ggplot2    * 3.1.0      2018-10-25 cran (@3.1.0) 
##  glue         1.3.0      2018-07-17 CRAN (R 3.5.0)
##  gower        0.1.2      2017-02-23 CRAN (R 3.5.0)
##  graphics   * 3.5.1      2018-07-05 local         
##  grDevices  * 3.5.1      2018-07-05 local         
##  grid         3.5.1      2018-07-05 local         
##  gtable       0.2.0      2016-02-26 CRAN (R 3.5.0)
##  haven        1.1.2      2018-06-27 CRAN (R 3.5.0)
##  hms          0.4.2      2018-03-10 CRAN (R 3.5.0)
##  htmltools    0.3.6      2017-04-28 CRAN (R 3.5.0)
##  httr         1.3.1      2017-08-20 CRAN (R 3.5.0)
##  ipred        0.9-7      2018-08-14 CRAN (R 3.5.0)
##  jsonlite     1.5        2017-06-01 CRAN (R 3.5.0)
##  kernlab      0.9-27     2018-08-10 CRAN (R 3.5.0)
##  knitr        1.20       2018-02-20 CRAN (R 3.5.0)
##  lattice      0.20-35    2017-03-25 CRAN (R 3.5.1)
##  lava         1.6.3      2018-08-10 CRAN (R 3.5.0)
##  lazyeval     0.2.1      2017-10-29 CRAN (R 3.5.0)
##  lubridate    1.7.4      2018-04-11 CRAN (R 3.5.0)
##  magic        1.5-8      2018-01-26 CRAN (R 3.5.0)
##  magrittr   * 1.5        2014-11-22 CRAN (R 3.5.0)
##  MASS         7.3-50     2018-04-30 CRAN (R 3.5.1)
##  Matrix       1.2-14     2018-04-13 CRAN (R 3.5.1)
##  memoise      1.1.0      2017-04-21 CRAN (R 3.5.0)
##  methods    * 3.5.1      2018-07-05 local         
##  modelr     * 0.1.2      2018-05-11 CRAN (R 3.5.0)
##  munsell      0.5.0      2018-06-12 CRAN (R 3.5.0)
##  nlme         3.1-137    2018-04-07 CRAN (R 3.5.1)
##  nnet         7.3-12     2016-02-02 CRAN (R 3.5.1)
##  pillar       1.3.0      2018-07-14 CRAN (R 3.5.0)
##  pkgconfig    2.0.2      2018-08-16 CRAN (R 3.5.1)
##  pls          2.6-0      2016-12-18 CRAN (R 3.5.0)
##  plyr         1.8.4      2016-06-08 CRAN (R 3.5.0)
##  prodlim      2018.04.18 2018-04-18 CRAN (R 3.5.0)
##  purrr      * 0.2.5      2018-05-29 CRAN (R 3.5.0)
##  R6           2.3.0      2018-10-04 cran (@2.3.0) 
##  Rcpp         1.0.0      2018-11-07 cran (@1.0.0) 
##  RcppRoll     0.3.0      2018-06-05 CRAN (R 3.5.0)
##  readr      * 1.1.1      2017-05-16 CRAN (R 3.5.0)
##  readxl       1.1.0      2018-04-20 CRAN (R 3.5.0)
##  recipes      0.1.3      2018-06-16 CRAN (R 3.5.0)
##  rlang        0.3.0.1    2018-10-25 CRAN (R 3.5.0)
##  rmarkdown    1.10       2018-06-11 CRAN (R 3.5.0)
##  robustbase   0.93-2     2018-07-27 CRAN (R 3.5.0)
##  rpart        4.1-13     2018-02-23 CRAN (R 3.5.0)
##  rprojroot    1.3-2      2018-01-03 CRAN (R 3.5.0)
##  rsample    * 0.0.2      2017-11-12 CRAN (R 3.5.0)
##  rstudioapi   0.7        2017-09-07 CRAN (R 3.5.0)
##  rvest        0.3.2      2016-06-17 CRAN (R 3.5.0)
##  scales       1.0.0      2018-08-09 CRAN (R 3.5.0)
##  sfsmisc      1.1-2      2018-03-05 CRAN (R 3.5.0)
##  splines      3.5.1      2018-07-05 local         
##  stats      * 3.5.1      2018-07-05 local         
##  stringi      1.2.4      2018-07-20 CRAN (R 3.5.0)
##  stringr    * 1.3.1      2018-05-10 CRAN (R 3.5.0)
##  survival     2.42-6     2018-07-13 CRAN (R 3.5.0)
##  tibble     * 1.4.2      2018-01-22 CRAN (R 3.5.0)
##  tidyr      * 0.8.1      2018-05-18 CRAN (R 3.5.0)
##  tidyselect   0.2.5      2018-10-11 cran (@0.2.5) 
##  tidyverse  * 1.2.1      2017-11-14 CRAN (R 3.5.0)
##  timeDate     3043.102   2018-02-21 CRAN (R 3.5.0)
##  tools        3.5.1      2018-07-05 local         
##  utils      * 3.5.1      2018-07-05 local         
##  withr        2.1.2      2018-03-15 CRAN (R 3.5.0)
##  xml2         1.2.0      2018-01-24 CRAN (R 3.5.0)
##  yaml         2.2.0      2018-07-25 CRAN (R 3.5.0)

  1. The actual value you use is irrelevant. Just be sure to set it in the script, otherwise R will randomly pick one each time you start a new session.

  2. The default family for glm() is gaussian(), or the Gaussian distribution. You probably know it by its other name, the Normal distribution.

LS0tCnRpdGxlOiAiU3RhdGlzdGljYWwgbGVhcm5pbmc6IHJlc2FtcGxpbmcgbWV0aG9kcyIKb3V0cHV0OgogIGh0bWxfZG9jdW1lbnQ6CiAgICB0b2M6IHRydWUKICAgIHRvY19mbG9hdDogdHJ1ZQotLS0KCmBgYHtyIHNldHVwLCBpbmNsdWRlID0gRkFMU0V9CmtuaXRyOjpvcHRzX2NodW5rJHNldChjYWNoZSA9IFRSVUUsCiAgICAgICAgICAgICAgICAgICAgICBtZXNzYWdlID0gRkFMU0UsCiAgICAgICAgICAgICAgICAgICAgICB3YXJuaW5nID0gRkFMU0UpCmBgYAoKYGBge3IgcGFja2FnZXMsIG1lc3NhZ2UgPSBGQUxTRSwgd2FybmluZyA9IEZBTFNFLCBjYWNoZSA9IEZBTFNFfQpsaWJyYXJ5KHRpZHl2ZXJzZSkKbGlicmFyeShtb2RlbHIpCmxpYnJhcnkocnNhbXBsZSkKbGlicmFyeShicm9vbSkKbGlicmFyeShtYWdyaXR0cikKCnNldC5zZWVkKDEyMzQpCgp0aGVtZV9zZXQodGhlbWVfbWluaW1hbCgpKQpgYGAKCiMgUmVzYW1wbGluZyBtZXRob2RzCgpSZXNhbXBsaW5nIG1ldGhvZHMgYXJlIGVzc2VudGlhbCB0byB0ZXN0IGFuZCBldmFsdWF0ZSBzdGF0aXN0aWNhbCBtb2RlbHMuIEJlY2F1c2UgeW91IGxpa2VseSBkbyBub3QgaGF2ZSB0aGUgcmVzb3VyY2VzIG9yIGNhcGFiaWxpdGllcyB0byByZXBlYXRlZGx5IHNhbXBsZSBmcm9tIHlvdXIgcG9wdWxhdGlvbiBvZiBpbnRlcmVzdCwgaW5zdGVhZCB5b3UgY2FuIHJlcGVhdGVkbHkgZHJhdyBmcm9tIHlvdXIgb3JpZ2luYWwgc2FtcGxlIHRvIG9idGFpbiBhZGRpdGlvbmFsIGluZm9ybWF0aW9uIGFib3V0IHlvdXIgbW9kZWwuIEZvciBpbnN0YW5jZSwgeW91IGNvdWxkIHJlcGVhdGVkbHkgZHJhdyBzYW1wbGVzIGZyb20geW91ciBkYXRhLCBlc3RpbWF0ZSBhIGxpbmVhciByZWdyZXNzaW9uIG1vZGVsIG9uIGVhY2ggc2FtcGxlLCBhbmQgdGhlbiBleGFtaW5lIGhvdyB0aGUgZXN0aW1hdGVkIG1vZGVsIGRpZmZlcnMgYWNyb3NzIGVhY2ggc2FtcGxlLiBUaGlzIGFsbG93cyB5b3UgdG8gYXNzZXNzIHRoZSB2YXJpYWJpbGl0eSBhbmQgc3RhYmlsaXR5IG9mIHlvdXIgbW9kZWwgaW4gYSB3YXkgbm90IHBvc3NpYmxlIGlmIHlvdSBjYW4gb25seSBmaXQgdGhlIG1vZGVsIG9uY2UuCgojIFZhbGlkYXRpb24gc2V0CgpPbmUgaXNzdWUgd2l0aCB1c2luZyB0aGUgc2FtZSBkYXRhIHRvIGJvdGggZml0IGFuZCBldmFsdWF0ZSBvdXIgbW9kZWwgaXMgdGhhdCB3ZSB3aWxsIGJpYXMgb3VyIG1vZGVsIHRvd2FyZHMgZml0dGluZyB0aGUgZGF0YSB0aGF0IHdlIGhhdmUuIFdlIG1heSBmaXQgb3VyIGZ1bmN0aW9uIHRvIGNyZWF0ZSB0aGUgcmVzdWx0cyB3ZSBleHBlY3Qgb3IgZGVzaXJlLCByYXRoZXIgdGhhbiB0aGUgInRydWUiIGZ1bmN0aW9uLiBJbnN0ZWFkLCB3ZSBjYW4gc3BsaXQgb3VyIGRhdGEgaW50byBkaXN0aW5jdCAqKnRyYWluaW5nKiogYW5kICoqdmFsaWRhdGlvbioqIHNldHMuIFRoZSB0cmFpbmluZyBzZXQgY2FuIGJlIHVzZWQgcmVwZWF0ZWRseSB0byBleHBsb3JlIG9yIHRyYWluIGRpZmZlcmVudCBtb2RlbHMuIE9uY2Ugd2UgaGF2ZSBhIHN0YWJsZSBtb2RlbCwgd2UgY2FuIGFwcGx5IGl0IHRvIHRoZSB2YWxpZGF0aW9uIHNldCBvZiBoZWxkLW91dCBkYXRhIHRvIGRldGVybWluZSAodW5iaWFzZWRseSkgd2hldGhlciB0aGUgbW9kZWwgbWFrZXMgYWNjdXJhdGUgcHJlZGljdGlvbnMuCgojIyBSZWdyZXNzaW9uCgpIZXJlIHdlIHdpbGwgZXhhbWluZSB0aGUgcmVsYXRpb25zaGlwIGJldHdlZW4gaG9yc2Vwb3dlciBhbmQgY2FyIG1pbGVhZ2UgaW4gdGhlIGBBdXRvYCBkYXRhc2V0IChmb3VuZCBpbiBgbGlicmFyeShJU0xSKWApOgoKYGBge3IgYXV0b30KbGlicmFyeShJU0xSKQoKQXV0byA8LSBhc190aWJibGUoQXV0bykKQXV0bwpgYGAKCmBgYHtyIGF1dG9fcGxvdCwgZGVwZW5kc29uPSJhdXRvIn0KZ2dwbG90KEF1dG8sIGFlcyhob3JzZXBvd2VyLCBtcGcpKSArCiAgZ2VvbV9wb2ludCgpCmBgYAoKVGhlIHJlbGF0aW9uc2hpcCBkb2VzIG5vdCBhcHBlYXIgdG8gYmUgc3RyaWN0bHkgbGluZWFyOgoKYGBge3IgYXV0b19wbG90X2xtLCBkZXBlbmRzb249ImF1dG8ifQpnZ3Bsb3QoQXV0bywgYWVzKGhvcnNlcG93ZXIsIG1wZykpICsKICBnZW9tX3BvaW50KCkgKwogIGdlb21fc21vb3RoKG1ldGhvZCA9ICJsbSIsIHNlID0gRkFMU0UpCmBgYAoKUGVyaGFwcyBieSBhZGRpbmcgW3F1YWRyYXRpYyB0ZXJtc10oc3RhdDAwM19sb2dpc3RpY19yZWdyZXNzaW9uLmh0bWwjcXVhZHJhdGljX3Rlcm1zKSB0byB0aGUgbGluZWFyIHJlZ3Jlc3Npb24gd2UgY291bGQgaW1wcm92ZSBvdmVyYWxsIG1vZGVsIGZpdC4gVG8gZXZhbHVhdGUgdGhlIG1vZGVsLCB3ZSB3aWxsIHNwbGl0IHRoZSBkYXRhIGludG8gYSB0cmFpbmluZyBzZXQgYW5kIHZhbGlkYXRpb24gc2V0LCBlc3RpbWF0ZSBhIHNlcmllcyBvZiBoaWdoZXItb3JkZXIgbW9kZWxzLCBhbmQgY2FsY3VsYXRlIGEgdGVzdCBzdGF0aXN0aWMgc3VtbWFyaXppbmcgdGhlIGFjY3VyYWN5IG9mIHRoZSBlc3RpbWF0ZWQgYG1wZ2AuIFRvIGNhbGN1bGF0ZSB0aGUgYWNjdXJhY3kgb2YgdGhlIG1vZGVsLCB3ZSB3aWxsIHVzZSAqKk1lYW4gU3F1YXJlZCBFcnJvcioqIChNU0UpLCBkZWZpbmVkIGFzCgokJE1TRSA9IFxmcmFjezF9e259IFxzdW1fe2kgPSAxfV57bn17KHlfaSAtIFxoYXR7Zn0oeF9pKSleMn0kJAoKd2hlcmU6CgoqICR5X2kgPSQgdGhlIG9ic2VydmVkIHJlc3BvbnNlIHZhbHVlIGZvciB0aGUgJGkkdGggb2JzZXJ2YXRpb24KKiAkXGhhdHtmfSh4X2kpID0kIHRoZSBwcmVkaWN0ZWQgcmVzcG9uc2UgdmFsdWUgZm9yIHRoZSAkaSR0aCBvYnNlcnZhdGlvbiBnaXZlbiBieSAkXGhhdHtmfSQKKiAkbiA9JCB0aGUgdG90YWwgbnVtYmVyIG9mIG9ic2VydmF0aW9ucwoKQm9vIG1hdGghIEFjdHVhbGx5IHRoaXMgaXMgcHJldHR5IGludHVpdGl2ZS4gQWxsIHdlJ3JlIGRvaW5nIGlzIGZvciBlYWNoIG9ic2VydmF0aW9uLCBjYWxjdWxhdGluZyB0aGUgZGlmZmVyZW5jZSBiZXR3ZWVuIHRoZSBhY3R1YWwgYW5kIHByZWRpY3RlZCB2YWx1ZXMgZm9yICR5JCwgc3F1YXJpbmcgdGhhdCBkaWZmZXJlbmNlLCB0aGVuIGNhbGN1bGF0aW5nIHRoZSBhdmVyYWdlIGFjcm9zcyBhbGwgb2JzZXJ2YXRpb25zLiBBbiBNU0Ugb2YgMCBpbmRpY2F0ZXMgdGhlIG1vZGVsIHBlcmZlY3RseSBwcmVkaWN0ZWQgZWFjaCBvYnNlcnZhdGlvbi4gVGhlIGxhcmdlciB0aGUgTVNFLCB0aGUgbW9yZSBlcnJvciBpbiB0aGUgbW9kZWwuCgpGb3IgdGhpcyB0YXNrLCBmaXJzdCB3ZSB1c2UgYHJzYW1wbGU6OmluaXRpYWxfc3BsaXQoKWAgdG8gY3JlYXRlIHRyYWluaW5nIGFuZCB2YWxpZGF0aW9uIHNldHMgKHVzaW5nIGEgNTAvNTAgc3BsaXQpLCB0aGVuIGVzdGltYXRlIGEgbGluZWFyIHJlZ3Jlc3Npb24gbW9kZWwgd2l0aG91dCBhbnkgcXVhZHJhdGljIHRlcm1zLgoKKiBJIHVzZSBgc2V0LnNlZWQoKWAgaW4gdGhlIGJlZ2lubmluZyAtIHdoZW5ldmVyIHlvdSBhcmUgd3JpdGluZyBhIHNjcmlwdCB0aGF0IGludm9sdmVzIHJhbmRvbWl6YXRpb24gKGhlcmUsIHJhbmRvbSBzdWJzZXR0aW5nIG9mIHRoZSBkYXRhKSwgYWx3YXlzIHNldCB0aGUgc2VlZCBhdCB0aGUgYmVnaW5uaW5nIG9mIHRoZSBzY3JpcHQuIFRoaXMgZW5zdXJlcyB0aGUgcmVzdWx0cyBjYW4gYmUgcmVwcm9kdWNlZCBwcmVjaXNlbHkuXltUaGUgYWN0dWFsIHZhbHVlIHlvdSB1c2UgaXMgaXJyZWxldmFudC4gSnVzdCBiZSBzdXJlIHRvIHNldCBpdCBpbiB0aGUgc2NyaXB0LCBvdGhlcndpc2UgUiB3aWxsIHJhbmRvbWx5IHBpY2sgb25lIGVhY2ggdGltZSB5b3Ugc3RhcnQgYSBuZXcgc2Vzc2lvbi5dCiogSSBhbHNvIHVzZSB0aGUgYGdsbSgpYCBmdW5jdGlvbiByYXRoZXIgdGhhbiBgbG0oKWAgLSBpZiB5b3UgZG9uJ3QgY2hhbmdlIHRoZSBgZmFtaWx5YCBwYXJhbWV0ZXIsIHRoZSByZXN1bHRzIG9mIGBsbSgpYCBhbmQgYGdsbSgpYCBhcmUgZXhhY3RseSB0aGUgc2FtZS5eW1RoZSBkZWZhdWx0IGBmYW1pbHlgIGZvciBgZ2xtKClgIGlzIGBnYXVzc2lhbigpYCwgb3IgdGhlICoqR2F1c3NpYW4qKiBkaXN0cmlidXRpb24uIFlvdSBwcm9iYWJseSBrbm93IGl0IGJ5IGl0cyBvdGhlciBuYW1lLCB0aGUgWyoqTm9ybWFsKiogZGlzdHJpYnV0aW9uXShodHRwczovL2VuLndpa2lwZWRpYS5vcmcvd2lraS9Ob3JtYWxfZGlzdHJpYnV0aW9uKS5dCgpgYGB7ciBhdXRvX3NwbGl0fQpzZXQuc2VlZCgxMjM0KQoKYXV0b19zcGxpdCA8LSBpbml0aWFsX3NwbGl0KGRhdGEgPSBBdXRvLCBwcm9wID0gMC41KQphdXRvX3RyYWluIDwtIHRyYWluaW5nKGF1dG9fc3BsaXQpCmF1dG9fdGVzdCA8LSB0ZXN0aW5nKGF1dG9fc3BsaXQpCmBgYAoKYGBge3IgYXV0b19sbSwgZGVwZW5kc29uPSJhdXRvX3NwbGl0In0KYXV0b19sbSA8LSBnbG0obXBnIH4gaG9yc2Vwb3dlciwgZGF0YSA9IGF1dG9fdHJhaW4pCnN1bW1hcnkoYXV0b19sbSkKYGBgCgpUbyBlc3RpbWF0ZSB0aGUgTVNFIGZvciBhIHNpbmdsZSBwYXJ0aXRpb24gKGkuZS4gZm9yIGEgdHJhaW5pbmcgb3IgdmFsaWRhdGlvbiBzZXQpOgoKMS4gVXNlIGBicm9vbTo6YXVnbWVudCgpYCB0byBnZW5lcmF0ZSBwcmVkaWN0ZWQgdmFsdWVzIGZvciB0aGUgZGF0YSBzZXQKMS4gQ2FsY3VsYXRlIHRoZSByZXNpZHVhbHMgYW5kIHNxdWFyZSBlYWNoIHZhbHVlCjEuIENhbGN1bGF0ZSB0aGUgbWVhbiBvZiBhbGwgdGhlIHNxdWFyZWQgcmVzaWR1YWxzIGluIHRoZSBkYXRhIHNldAoKRm9yIHRoZSB0cmFpbmluZyBzZXQsIHRoaXMgd291bGQgbG9vayBsaWtlOgoKYGBge3IgbXNlLXRyYWluLCBkZXBlbmRzb24gPSAiYXV0b19sbSJ9Cih0cmFpbl9tc2UgPC0gYXVnbWVudChhdXRvX2xtLCBuZXdkYXRhID0gYXV0b190cmFpbikgJT4lCiAgbXV0YXRlKC5yZXNpZCA9IG1wZyAtIC5maXR0ZWQsCiAgICAgICAgIC5yZXNpZDIgPSAucmVzaWQgXiAyKSAlJCUKICBtZWFuKC5yZXNpZDIpKQpgYGAKCj4gTm90ZSB0aGUgc3BlY2lhbCB1c2Ugb2YgdGhlIFtgJCUkYCBwaXBlIG9wZXJhdG9yIGZyb20gdGhlIGBtYWdyaXR0cmAgcGFja2FnZV0oaHR0cDovL3I0ZHMuaGFkLmNvLm56L3BpcGVzLmh0bWwjb3RoZXItdG9vbHMtZnJvbS1tYWdyaXR0cikuIFRoaXMgYWxsb3dzIHVzIHRvIGRpcmVjdGx5IGFjY2VzcyBjb2x1bW5zIGZyb20gdGhlIGRhdGEgZnJhbWUgZW50ZXJpbmcgdGhlIHBpcGUuIFRoaXMgaXMgZXNwZWNpYWxseSB1c2VmdWwgZm9yIGludGVncmF0aW5nIG5vbi10aWR5IGZ1bmN0aW9ucyBpbnRvIGEgdGlkeSBvcGVyYXRpb24uCgpGb3IgdGhlIHZhbGlkYXRpb24gc2V0OgoKYGBge3IgbXNlLXRlc3QsIGRlcGVuZHNvbiA9ICJhdXRvX2xtIn0KKHRlc3RfbXNlIDwtIGF1Z21lbnQoYXV0b19sbSwgbmV3ZGF0YSA9IGF1dG9fdGVzdCkgJT4lCiAgbXV0YXRlKC5yZXNpZCA9IG1wZyAtIC5maXR0ZWQsCiAgICAgICAgIC5yZXNpZDIgPSAucmVzaWQgXiAyKSAlJCUKICBtZWFuKC5yZXNpZDIpKQpgYGAKCkZvciBhIHN0cmljdGx5IGxpbmVhciBtb2RlbCwgdGhlIE1TRSBmb3IgdGhlIHZhbGlkYXRpb24gc2V0IGlzIGByIGZvcm1hdEModGVzdF9tc2UsIGRpZ2l0cyA9IDQpYC4gSG93IGRvZXMgdGhpcyBjb21wYXJlIHRvIGEgcXVhZHJhdGljIG1vZGVsPyBXZSBjYW4gdXNlIHRoZSBgcG9seSgpYCBmdW5jdGlvbiBpbiBjb25qdW5jdGlvbiB3aXRoIGEgYG1hcCgpYCBpdGVyYXRpb24gdG8gZXN0aW1hdGUgdGhlIE1TRSBmb3IgYSBzZXJpZXMgb2YgbW9kZWxzIHdpdGggaGlnaGVyLW9yZGVyIHBvbHlub21pYWwgdGVybXM6CgpgYGB7ciBtc2UtcG9seSwgZGVwZW5kc29uID0gImF1dG9fc3BsaXQifQojIHZpc3VhbGl6ZSBlYWNoIG1vZGVsCmdncGxvdChBdXRvLCBhZXMoaG9yc2Vwb3dlciwgbXBnKSkgKwogIGdlb21fcG9pbnQoYWxwaGEgPSAuMSkgKwogIGdlb21fc21vb3RoKGFlcyhjb2xvciA9ICIxIiksCiAgICAgICAgICAgICAgbWV0aG9kID0gImdsbSIsCiAgICAgICAgICAgICAgZm9ybXVsYSA9IHkgfiBwb2x5KHgsIGkgPSAxKSwKICAgICAgICAgICAgICBzZSA9IEZBTFNFKSArCiAgZ2VvbV9zbW9vdGgoYWVzKGNvbG9yID0gIjIiKSwKICAgICAgICAgICAgICBtZXRob2QgPSAiZ2xtIiwKICAgICAgICAgICAgICBmb3JtdWxhID0geSB+IHBvbHkoeCwgaSA9IDIpLAogICAgICAgICAgICAgIHNlID0gRkFMU0UpICsKICBnZW9tX3Ntb290aChhZXMoY29sb3IgPSAiMyIpLAogICAgICAgICAgICAgIG1ldGhvZCA9ICJnbG0iLAogICAgICAgICAgICAgIGZvcm11bGEgPSB5IH4gcG9seSh4LCBpID0gMyksCiAgICAgICAgICAgICAgc2UgPSBGQUxTRSkgKwogIGdlb21fc21vb3RoKGFlcyhjb2xvciA9ICI0IiksCiAgICAgICAgICAgICAgbWV0aG9kID0gImdsbSIsCiAgICAgICAgICAgICAgZm9ybXVsYSA9IHkgfiBwb2x5KHgsIGkgPSA0KSwKICAgICAgICAgICAgICBzZSA9IEZBTFNFKSArCiAgZ2VvbV9zbW9vdGgoYWVzKGNvbG9yID0gIjUiKSwKICAgICAgICAgICAgICBtZXRob2QgPSAiZ2xtIiwKICAgICAgICAgICAgICBmb3JtdWxhID0geSB+IHBvbHkoeCwgaSA9IDUpLAogICAgICAgICAgICAgIHNlID0gRkFMU0UpICsKICBzY2FsZV9jb2xvcl9icmV3ZXIodHlwZSA9ICJxdWFsIiwgcGFsZXR0ZSA9ICJEYXJrMiIpICsKICBsYWJzKHggPSAiSG9yc2Vwb3dlciIsCiAgICAgICB5ID0gIk1QRyIsCiAgICAgICBjb2xvciA9ICJIaWdoZXN0LW9yZGVyXG5wb2x5bm9taWFsIikKCiMgZnVuY3Rpb24gdG8gZXN0aW1hdGUgbW9kZWwgdXNpbmcgdHJhaW5pbmcgc2V0IGFuZCBnZW5lcmF0ZSBmaXQgc3RhdGlzdGljcwojIHVzaW5nIHRoZSB0ZXN0IHNldApwb2x5X3Jlc3VsdHMgPC0gZnVuY3Rpb24odHJhaW4sIHRlc3QsIGkpIHsKICAjIEZpdCB0aGUgbW9kZWwgdG8gdGhlIHRyYWluaW5nIHNldAogIG1vZCA8LSBnbG0obXBnIH4gcG9seShob3JzZXBvd2VyLCBpKSwgZGF0YSA9IHRyYWluKQogIAogICMgYGF1Z21lbnRgIHdpbGwgc2F2ZSB0aGUgcHJlZGljdGlvbnMgd2l0aCB0aGUgdGVzdCBkYXRhIHNldAogIHJlcyA8LSBhdWdtZW50KG1vZCwgbmV3ZGF0YSA9IHRlc3QpICU+JQogICAgIyBjYWxjdWxhdGUgcmVzaWR1YWxzIGZvciBmdXR1cmUgdXNlCiAgICBtdXRhdGUoLnJlc2lkID0gbXBnIC0gLmZpdHRlZCkKICAKICAjIFJldHVybiB0aGUgdGVzdCBkYXRhIHNldCB3aXRoIHRoZSBhZGRpdGlvbmFsIGNvbHVtbnMKICByZXMKfQoKIyBmdW5jdGlvbiB0byByZXR1cm4gTVNFIGZvciBhIHNwZWNpZmljIGhpZ2hlci1vcmRlciBwb2x5bm9taWFsIHRlcm0KcG9seV9tc2UgPC0gZnVuY3Rpb24oaSwgdHJhaW4sIHRlc3QpewogIHBvbHlfcmVzdWx0cyh0cmFpbiwgdGVzdCwgaSkgJSQlCiAgICBtZWFuKC5yZXNpZCBeIDIpCn0KCmN2X21zZSA8LSBkYXRhX2ZyYW1lKHRlcm1zID0gc2VxKGZyb20gPSAxLCB0byA9IDUpLAogICAgICAgICAgICAgICAgICAgICBtc2VfdGVzdCA9IG1hcF9kYmwodGVybXMsIHBvbHlfbXNlLCBhdXRvX3RyYWluLCBhdXRvX3Rlc3QpKQoKZ2dwbG90KGN2X21zZSwgYWVzKHRlcm1zLCBtc2VfdGVzdCkpICsKICBnZW9tX2xpbmUoKSArCiAgbGFicyh0aXRsZSA9ICJDb21wYXJpbmcgcXVhZHJhdGljIGxpbmVhciBtb2RlbHMiLAogICAgICAgc3VidGl0bGUgPSAiVXNpbmcgdmFsaWRhdGlvbiBzZXQiLAogICAgICAgeCA9ICJIaWdoZXN0LW9yZGVyIHBvbHlub21pYWwiLAogICAgICAgeSA9ICJNZWFuIFNxdWFyZWQgRXJyb3IiKQpgYGAKCkJhc2VkIG9uIHRoZSBNU0UgZm9yIHRoZSB2YWxpZGF0aW9uIHNldCwgYSBwb2x5bm9taWFsIG1vZGVsIHdpdGggYSBxdWFkcmF0aWMgdGVybSAoJFx0ZXh0e2hvcnNlcG93ZXJ9XjIkKSBwcm9kdWNlcyB0aGUgbG93ZXN0IGF2ZXJhZ2UgZXJyb3IuIEFkZGluZyBjdWJpYyBvciBoaWdoZXItb3JkZXIgdGVybXMgaXMganVzdCBub3QgbmVjZXNzYXJ5LgoKIyMgQ2xhc3NpZmljYXRpb24KClJlY2FsbCBvdXIgZWZmb3J0cyB0byBbcHJlZGljdCBwYXNzZW5nZXIgc3Vydml2YWwgZHVyaW5nIHRoZSBzaW5raW5nIG9mIHRoZSBUaXRhbmljXShzdGF0MDAzX2xvZ2lzdGljX3JlZ3Jlc3Npb24uaHRtbCNpbnRlcmFjdGl2ZV90ZXJtcykuCgpgYGB7ciB0aXRhbmljX2RhdGEsIG1lc3NhZ2UgPSBGQUxTRX0KbGlicmFyeSh0aXRhbmljKQp0aXRhbmljIDwtIGFzX3RpYmJsZSh0aXRhbmljX3RyYWluKQoKdGl0YW5pYyAlPiUKICBoZWFkKCkgJT4lCiAga25pdHI6OmthYmxlKCkKYGBgCgpgYGB7ciBhZ2Vfd29tYW5fY3Jvc3N9CnN1cnZpdmVfYWdlX3dvbWFuX3ggPC0gZ2xtKFN1cnZpdmVkIH4gQWdlICogU2V4LCBkYXRhID0gdGl0YW5pYywKICAgICAgICAgICAgICAgICAgICAgICAgICAgZmFtaWx5ID0gYmlub21pYWwpCnN1bW1hcnkoc3Vydml2ZV9hZ2Vfd29tYW5feCkKYGBgCgpXZSBjYW4gdXNlIHRoZSBzYW1lIHZhbGlkYXRpb24gc2V0IGFwcHJvYWNoIHRvIGV2YWx1YXRlIHRoZSBtb2RlbCdzIGFjY3VyYWN5LiBGb3IgY2xhc3NpZmljYXRpb24gbW9kZWxzLCBpbnN0ZWFkIG9mIHVzaW5nIE1TRSB3ZSBleGFtaW5lIHRoZSAqKnRlc3QgZXJyb3IgcmF0ZSoqLiBUaGF0IGlzLCBvZiBhbGwgdGhlIHByZWRpY3Rpb25zIGdlbmVyYXRlZCBmb3IgdGhlIHRlc3Qgc2V0LCB3aGF0IHBlcmNlbnRhZ2Ugb2YgcHJlZGljdGlvbnMgYXJlIGluY29ycmVjdD8gVGhlIGdvYWwgaXMgdG8gbWluaW1pemUgdGhpcyB2YWx1ZSBhcyBtdWNoIGFzIHBvc3NpYmxlIChpZGVhbGx5LCB1bnRpbCB3ZSBtYWtlIG5vIGVycm9ycyBhbmQgb3VyIGVycm9yIHJhdGUgaXMgJDAlJCkuCgpgYGB7ciBsb2dpdH0KIyBmdW5jdGlvbiB0byBjb252ZXJ0IGxvZy1vZGRzIHRvIHByb2JhYmlsaXRpZXMKbG9naXQycHJvYiA8LSBmdW5jdGlvbih4KXsKICBleHAoeCkgLyAoMSArIGV4cCh4KSkKfQpgYGAKCmBgYHtyIGFjY3VyYWN5X2FnZV9nZW5kZXJfeF90ZXN0X3NldCwgZGVwZW5kc29uPSJhZ2Vfd29tYW5fY3Jvc3MiLCBtZXNzYWdlID0gRkFMU0V9CiMgc3BsaXQgdGhlIGRhdGEgaW50byB0cmFpbmluZyBhbmQgdmFsaWRhdGlvbiBzZXRzCnRpdGFuaWNfc3BsaXQgPC0gaW5pdGlhbF9zcGxpdChkYXRhID0gdGl0YW5pYywgcHJvcCA9IDAuNSkKCiMgZml0IG1vZGVsIHRvIHRyYWluaW5nIGRhdGEKdHJhaW5fbW9kZWwgPC0gZ2xtKFN1cnZpdmVkIH4gQWdlICogU2V4LCBkYXRhID0gdHJhaW5pbmcodGl0YW5pY19zcGxpdCksCiAgICAgICAgICAgICAgICAgICBmYW1pbHkgPSBiaW5vbWlhbCkKc3VtbWFyeSh0cmFpbl9tb2RlbCkKCiMgY2FsY3VsYXRlIHByZWRpY3Rpb25zIHVzaW5nIHZhbGlkYXRpb24gc2V0CnhfdGVzdF9hY2N1cmFjeSA8LSBhdWdtZW50KHRyYWluX21vZGVsLCBuZXdkYXRhID0gdGVzdGluZyh0aXRhbmljX3NwbGl0KSkgJT4lIAogIGFzX3RpYmJsZSgpICU+JQogIG11dGF0ZShwcmVkID0gbG9naXQycHJvYiguZml0dGVkKSwKICAgICAgICAgcHJlZCA9IGFzLm51bWVyaWMocHJlZCA+IC41KSkKCiMgY2FsY3VsYXRlIHRlc3QgZXJyb3IgcmF0ZQptZWFuKHhfdGVzdF9hY2N1cmFjeSRTdXJ2aXZlZCAhPSB4X3Rlc3RfYWNjdXJhY3kkcHJlZCwgbmEucm0gPSBUUlVFKQpgYGAKClRoaXMgaW50ZXJhY3RpdmUgbW9kZWwgZ2VuZXJhdGVzIGFuIGVycm9yIHJhdGUgb2YgYHIgZm9ybWF0QyhtZWFuKHhfdGVzdF9hY2N1cmFjeSRTdXJ2aXZlZCAhPSB4X3Rlc3RfYWNjdXJhY3kkcHJlZCwgbmEucm0gPSBUUlVFKSAqIDEwMCwgZGlnaXRzID0gMylgJS4gV2UgY291bGQgY29tcGFyZSB0aGlzIGVycm9yIHJhdGUgdG8gYWx0ZXJuYXRpdmUgY2xhc3NpZmljYXRpb24gbW9kZWxzLCBlaXRoZXIgb3RoZXIgbG9naXN0aWMgcmVncmVzc2lvbiBtb2RlbHMgKHVzaW5nIGRpZmZlcmVudCBmb3JtdWxhcykgb3IgYSB0cmVlLWJhc2VkIG1ldGhvZC4KCiMjIERyYXdiYWNrcyB0byB2YWxpZGF0aW9uIHNldHMKClRoZXJlIGFyZSB0d28gbWFpbiBwcm9ibGVtcyB3aXRoIHZhbGlkYXRpb24gc2V0czoKCjEuIFZhbGlkYXRpb24gZXN0aW1hdGVzIG9mIHRoZSB0ZXN0IGVycm9yIHJhdGVzIGNhbiBiZSBoaWdobHkgdmFyaWFibGUgZGVwZW5kaW5nIG9uIHdoaWNoIG9ic2VydmF0aW9ucyBhcmUgc2FtcGxlZCBpbnRvIHRoZSB0cmFpbmluZyBhbmQgdGVzdCBzZXRzLiBTZWUgd2hhdCBoYXBwZW5zIGlmIHdlIHJlcGVhdCB0aGUgc2FtcGxpbmcsIGVzdGltYXRpb24sIGFuZCB2YWxpZGF0aW9uIHByb2NlZHVyZSBmb3IgdGhlIGBBdXRvYCBkYXRhIHNldDoKCiAgICBgYGB7ciBhdXRvX3ZhcmlhYmxlX21zZX0KICAgIG1zZV92YXJpYWJsZSA8LSBmdW5jdGlvbihBdXRvKXsKICAgICAgYXV0b19zcGxpdCA8LSBpbml0aWFsX3NwbGl0KEF1dG8sIHByb3AgPSAwLjUpCiAgICAgIGF1dG9fdHJhaW4gPC0gdHJhaW5pbmcoYXV0b19zcGxpdCkKICAgICAgYXV0b190ZXN0IDwtIHRlc3RpbmcoYXV0b19zcGxpdCkKICAgICAgCiAgICAgIGN2X21zZSA8LSBkYXRhX2ZyYW1lKHRlcm1zID0gc2VxKGZyb20gPSAxLCB0byA9IDUpLAogICAgICAgICAgICAgICAgICAgICAgICAgICBtc2VfdGVzdCA9IG1hcF9kYmwodGVybXMsIHBvbHlfbXNlLCBhdXRvX3RyYWluLCBhdXRvX3Rlc3QpKQogICAgICAKICAgICAgcmV0dXJuKGN2X21zZSkKICAgIH0KICAgIAogICAgcmVydW4oMTAsIG1zZV92YXJpYWJsZShBdXRvKSkgJT4lCiAgICAgIGJpbmRfcm93cyguaWQgPSAiaWQiKSAlPiUKICAgICAgZ2dwbG90KGFlcyh0ZXJtcywgbXNlX3Rlc3QsIGNvbG9yID0gaWQpKSArCiAgICAgIGdlb21fbGluZSgpICsKICAgICAgbGFicyh0aXRsZSA9ICJWYXJpYWJpbGl0eSBvZiBNU0UgZXN0aW1hdGVzIiwKICAgICAgICAgICBzdWJ0aXRsZSA9ICJVc2luZyB0aGUgdmFsaWRhdGlvbiBzZXQgYXBwcm9hY2giLAogICAgICAgICAgIHggPSAiRGVncmVlIG9mIFBvbHlub21pYWwiLAogICAgICAgICAgIHkgPSAiTWVhbiBTcXVhcmVkIEVycm9yIikgKwogICAgICB0aGVtZShsZWdlbmQucG9zaXRpb24gPSAibm9uZSIpCiAgICBgYGAKICAgIAogICAgRGVwZW5kaW5nIG9uIHRoZSBzcGVjaWZpYyB0cmFpbmluZy90ZXN0IHNwbGl0LCBvdXIgTVNFIHZhcmllcyBieSB1cCB0byA1LgoKMS4gSWYgeW91IGRvbid0IGhhdmUgYSBsYXJnZSBkYXRhIHNldCwgeW91J2xsIGhhdmUgdG8gZHJhbWF0aWNhbGx5IHNocmluayB0aGUgc2l6ZSBvZiB5b3VyIHRyYWluaW5nIHNldC4gTW9zdCBzdGF0aXN0aWNhbCBsZWFybmluZyBtZXRob2RzIHBlcmZvcm0gYmV0dGVyIHdpdGggbW9yZSBvYnNlcnZhdGlvbnMgLSBpZiB5b3UgZG9uJ3QgaGF2ZSBlbm91Z2ggZGF0YSBpbiB0aGUgdHJhaW5pbmcgc2V0LCB5b3UgbWlnaHQgb3ZlcmVzdGltYXRlIHRoZSBlcnJvciByYXRlIGluIHRoZSB0ZXN0IHNldC4KCiMgTGVhdmUtb25lLW91dCBjcm9zcy12YWxpZGF0aW9uCgpBbiBhbHRlcm5hdGl2ZSBtZXRob2QgaXMgKipsZWF2ZS1vbmUtb3V0IGNyb3NzIHZhbGlkYXRpb24qKiAoTE9PQ1YpLiBMaWtlIHdpdGggdGhlIHZhbGlkYXRpb24gc2V0IGFwcHJvYWNoLCB5b3Ugc3BsaXQgdGhlIGRhdGEgaW50byB0d28gcGFydHMuIEhvd2V2ZXIgdGhlIGRpZmZlcmVuY2UgaXMgdGhhdCB5b3Ugb25seSByZW1vdmUgb25lIG9ic2VydmF0aW9uIGZvciB0aGUgdGVzdCBzZXQsIGFuZCBrZWVwIGFsbCByZW1haW5pbmcgb2JzZXJ2YXRpb25zIGluIHRoZSB0cmFpbmluZyBzZXQuIFRoZSBzdGF0aXN0aWNhbCBsZWFybmluZyBtZXRob2QgaXMgZml0IG9uIHRoZSAkbi0xJCB0cmFpbmluZyBzZXQuIFlvdSB0aGVuIHVzZSB0aGUgaGVsZC1vdXQgb2JzZXJ2YXRpb24gdG8gY2FsY3VsYXRlIHRoZSAkTVNFID0gKHlfMSAtIFxoYXR7eX1fMSleMiQgd2hpY2ggc2hvdWxkIGJlIGFuIHVuYmlhc2VkIGVzdGltYXRvciBvZiB0aGUgdGVzdCBlcnJvci4gQmVjYXVzZSB0aGlzIE1TRSBpcyBoaWdobHkgZGVwZW5kZW50IG9uIHdoaWNoIG9ic2VydmF0aW9uIGlzIGhlbGQgb3V0LCAqKndlIHJlcGVhdCB0aGlzIHByb2Nlc3MgZm9yIGV2ZXJ5IHNpbmdsZSBvYnNlcnZhdGlvbiBpbiB0aGUgZGF0YSBzZXQqKi4gTWF0aGVtYXRpY2FsbHksIHRoaXMgbG9va3MgbGlrZToKCiQkQ1ZfeyhuKX0gPSBcZnJhY3sxfXtufSBcc3VtX3tpID0gMX1ee259e01TRV9pfSQkCgpUaGlzIG1ldGhvZCBwcm9kdWNlcyBlc3RpbWF0ZXMgb2YgdGhlIGVycm9yIHJhdGUgdGhhdCBoYXZlIG1pbmltYWwgYmlhcyBhbmQgYXJlIHJlbGF0aXZlbHkgc3RlYWR5IChpLmUuIG5vbi12YXJ5aW5nKSwgdW5saWtlIHRoZSB2YWxpZGF0aW9uIHNldCBhcHByb2FjaCB3aGVyZSB0aGUgTVNFIGVzdGltYXRlIGlzIGhpZ2hseSBkZXBlbmRlbnQgb24gdGhlIHNhbXBsaW5nIHByb2Nlc3MgZm9yIHRyYWluaW5nL3Rlc3Qgc2V0cy4gTE9PQ1YgaXMgYWxzbyBoaWdobHkgZmxleGlibGUgYW5kIHdvcmtzIHdpdGggYW55IGtpbmQgb2YgcHJlZGljdGl2ZSBtb2RlbGluZy4KCk9mIGNvdXJzZSB0aGUgZG93bnNpZGUgaXMgdGhhdCB0aGlzIG1ldGhvZCBpcyBjb21wdXRhdGlvbmFsbHkgZGlmZmljdWx0LiBZb3UgaGF2ZSB0byBlc3RpbWF0ZSAkbiQgZGlmZmVyZW50IG1vZGVscyAtIGlmIHlvdSBoYXZlIGEgbGFyZ2UgJG4kIG9yIGVhY2ggaW5kaXZpZHVhbCBtb2RlbCB0YWtlcyBhIGxvbmcgdGltZSB0byBjb21wdXRlLCB5b3UgbWF5IGJlIHN0dWNrIHdhaXRpbmcgYSBsb25nIHRpbWUgZm9yIHRoZSBjb21wdXRlciB0byBmaW5pc2ggaXRzIGNhbGN1bGF0aW9ucy4KCiMjIExPT0NWIGluIGxpbmVhciByZWdyZXNzaW9uCgpXZSBjYW4gdXNlIHRoZSBgbG9vX2N2KClgIGZ1bmN0aW9uIGluIHRoZSBgcnNhbXBsZWAgbGlicmFyeSB0byBjb21wdXRlIHRoZSBMT09DViBvZiBhbnkgbGluZWFyIG9yIGxvZ2lzdGljIHJlZ3Jlc3Npb24gbW9kZWwuIEl0IHRha2VzIGEgc2luZ2xlIGFyZ3VtZW50OiB0aGUgZGF0YSBmcmFtZSBiZWluZyBjcm9zcy12YWxpZGF0ZWQuIEZvciB0aGUgYEF1dG9gIGRhdGFzZXQsIHRoaXMgbG9va3MgbGlrZToKCmBgYHtyIGxvb2N2LWRhdGEsIGRlcGVuZHNvbj0iQXV0byJ9Cmxvb2N2X2RhdGEgPC0gbG9vX2N2KEF1dG8pCmxvb2N2X2RhdGEKYGBgCgpFYWNoIGVsZW1lbnQgb2YgYGxvb2N2X2RhdGEkc3BsaXRzYCBpcyBhbiBvYmplY3Qgb2YgY2xhc3MgYHJzcGxpdGAuIFRoaXMgaXMgZXNzZW50aWFsbHkgYW4gZWZmaWNpZW50IGNvbnRhaW5lciBmb3Igc3RvcmluZyBib3RoIHRoZSAqKmFuYWx5c2lzKiogZGF0YSAoaS5lLiB0aGUgdHJhaW5pbmcgZGF0YSBzZXQpIGFuZCB0aGUgKiphc3Nlc3NtZW50KiogZGF0YSAoaS5lLiB0aGUgdmFsaWRhdGlvbiBkYXRhIHNldCkuIElmIHdlIHByaW50IHRoZSBjb250ZW50cyBvZiBhIHNpbmdsZSBgcnNwbGl0YCBvYmplY3Q6CgpgYGB7ciByc3BsaXQsIGRlcGVuZHNvbiA9ICJsb29jdi1kYXRhIn0KZmlyc3RfcmVzYW1wbGUgPC0gbG9vY3ZfZGF0YSRzcGxpdHNbWzFdXQpmaXJzdF9yZXNhbXBsZQpgYGAKClRoaXMgdGVsbHMgdXMgdGhlcmUgYXJlIGByIGRpbShmaXJzdF9yZXNhbXBsZSlbWyJhbmFseXNpcyJdXWAgb2JzZXJ2YXRpb25zIGluIHRoZSBhbmFseXNpcyBzZXQsIGByIGRpbShmaXJzdF9yZXNhbXBsZSlbWyJhc3Nlc3NtZW50Il1dYCBvYnNlcnZhdGlvbiBpbiB0aGUgYXNzZXNzbWVudCBzZXQsIGFuZCB0aGUgb3JpZ2luYWwgZGF0YSBzZXQgY29udGFpbmVkIGByIGRpbShmaXJzdF9yZXNhbXBsZSlbWyJuIl1dYCBvYnNlcnZhdGlvbnMuIFRvIGV4dHJhY3QgdGhlIGFuYWx5c2lzL2Fzc2Vzc21lbnQgc2V0cywgdXNlIGBhbmFseXNpcygpYCBvciBgYXNzZXNzbWVudCgpYCByZXNwZWN0aXZlbHk6CgpgYGB7ciByc3BsaXQtZXh0cmFjdH0KdHJhaW5pbmcoZmlyc3RfcmVzYW1wbGUpCmFzc2Vzc21lbnQoZmlyc3RfcmVzYW1wbGUpCmBgYAoKR2l2ZW4gdGhpcyBuZXcgYGxvb2N2X2RhdGFgIGRhdGEgZnJhbWUsIHdlIHdyaXRlIGEgZnVuY3Rpb24gdGhhdCB3aWxsLCBmb3IgZWFjaCByZXNhbXBsZToKCjEuIE9idGFpbiB0aGUgYW5hbHlzaXMgZGF0YSBzZXQgKGkuZS4gdGhlICRuLTEkIHRyYWluaW5nIHNldCkKMS4gRml0IGEgbGluZWFyIHJlZ3Jlc3Npb24gbW9kZWwKMS4gUHJlZGljdCB0aGUgdGVzdCBkYXRhIChhbHNvIGtub3duIGFzIHRoZSAqKmFzc2Vzc21lbnQqKiBkYXRhLCB0aGUgJDEkIHRlc3Qgc2V0KSB1c2luZyB0aGUgYGJyb29tYCBwYWNrYWdlCjEuIERldGVybWluZSB0aGUgTVNFIGZvciBlYWNoIHNhbXBsZQoKYGBge3IgbG9vY3YtZnVuY3Rpb24sIGRlcGVuZHNvbiA9ICJBdXRvIn0KaG9sZG91dF9yZXN1bHRzIDwtIGZ1bmN0aW9uKHNwbGl0cykgewogICMgRml0IHRoZSBtb2RlbCB0byB0aGUgbi0xCiAgbW9kIDwtIGdsbShtcGcgfiBob3JzZXBvd2VyLCBkYXRhID0gYW5hbHlzaXMoc3BsaXRzKSkKICAKICAjIFNhdmUgdGhlIGhlbGRvdXQgb2JzZXJ2YXRpb24KICBob2xkb3V0IDwtIGFzc2Vzc21lbnQoc3BsaXRzKQogIAogICMgYGF1Z21lbnRgIHdpbGwgc2F2ZSB0aGUgcHJlZGljdGlvbnMgd2l0aCB0aGUgaG9sZG91dCBkYXRhIHNldAogIHJlcyA8LSBhdWdtZW50KG1vZCwgbmV3ZGF0YSA9IGhvbGRvdXQpICU+JQogICAgIyBjYWxjdWxhdGUgcmVzaWR1YWxzIGZvciBmdXR1cmUgdXNlCiAgICBtdXRhdGUoLnJlc2lkID0gbXBnIC0gLmZpdHRlZCkKICAKICAjIFJldHVybiB0aGUgYXNzZXNzbWVudCBkYXRhIHNldCB3aXRoIHRoZSBhZGRpdGlvbmFsIGNvbHVtbnMKICByZXMKfQpgYGAKClRoaXMgZnVuY3Rpb24gd29ya3MgZm9yIGEgc2luZ2xlIHJlc2FtcGxlOgoKYGBge3IgbG9vY3YtZnVuY3Rpb24tdGVzdCwgZGVwZW5kc29uID0gImxvb2N2LWZ1bmN0aW9uIn0KaG9sZG91dF9yZXN1bHRzKGxvb2N2X2RhdGEkc3BsaXRzW1sxXV0pCmBgYAoKVG8gY29tcHV0ZSB0aGUgTVNFIGZvciBlYWNoIGhlbGRvdXQgb2JzZXJ2YXRpb24gKGkuZS4gZXN0aW1hdGUgdGhlIHRlc3QgTVNFIGZvciBlYWNoIG9mIHRoZSAkbiQgb2JzZXJ2YXRpb25zKSwgd2UgdXNlIHRoZSBgbWFwKClgIGZ1bmN0aW9uIGZyb20gdGhlIGBwdXJycmAgcGFja2FnZSB0byBlc3RpbWF0ZSB0aGUgbW9kZWwgZm9yIGVhY2ggdHJhaW5pbmcgdGVzdCwgdGhlbiBjYWxjdWxhdGUgdGhlIE1TRSBmb3IgZWFjaCBvYnNlcnZhdGlvbiBpbiBlYWNoIHRlc3Qgc2V0OgoKYGBge3IgbG9vY3YsIGRlcGVuZHNvbiA9IGMoIkF1dG8iLCAibG9vY3YtZnVuY3Rpb24iKX0KbG9vY3ZfZGF0YSRyZXN1bHRzIDwtIG1hcChsb29jdl9kYXRhJHNwbGl0cywgaG9sZG91dF9yZXN1bHRzKQpsb29jdl9kYXRhJG1zZSA8LSBtYXBfZGJsKGxvb2N2X2RhdGEkcmVzdWx0cywgfiBtZWFuKC4kLnJlc2lkIF4gMikpCmxvb2N2X2RhdGEKYGBgCgpOb3cgd2UgY2FuIGNvbXB1dGUgdGhlIG92ZXJhbGwgTE9PQ1YgTVNFIGZvciB0aGUgZGF0YSBzZXQgYnkgY2FsY3VsYXRpbmcgdGhlIG1lYW4gb2YgdGhlIGBtc2VgIGNvbHVtbjoKCmBgYHtyIGxvb2N2LXRlc3QtbXNlLCBkZXBlbmRzb24gPSBjKCJBdXRvIiwgImxvb2N2LWZ1bmN0aW9uIil9Cmxvb2N2X2RhdGEgJT4lCiAgc3VtbWFyaXplKG1zZSA9IG1lYW4obXNlKSkKYGBgCgpXZSBjYW4gYWxzbyB1c2UgdGhpcyBtZXRob2QgdG8gY29tcGFyZSB0aGUgb3B0aW1hbCBudW1iZXIgb2YgcG9seW5vbWlhbCB0ZXJtcyBhcyBiZWZvcmUuCgpgYGB7ciBsb29jdl9wb2x5LCBkZXBlbmRzb249IkF1dG8ifQojIG1vZGlmaWVkIGZ1bmN0aW9uIHRvIGVzdGltYXRlIG1vZGVsIHdpdGggdmFyeWluZyBoaWdoZXN0IG9yZGVyIHBvbHlub21pYWwKaG9sZG91dF9yZXN1bHRzIDwtIGZ1bmN0aW9uKHNwbGl0cywgaSkgewogICMgRml0IHRoZSBtb2RlbCB0byB0aGUgbi0xCiAgbW9kIDwtIGdsbShtcGcgfiBwb2x5KGhvcnNlcG93ZXIsIGkpLCBkYXRhID0gYW5hbHlzaXMoc3BsaXRzKSkKICAKICAjIFNhdmUgdGhlIGhlbGRvdXQgb2JzZXJ2YXRpb24KICBob2xkb3V0IDwtIGFzc2Vzc21lbnQoc3BsaXRzKQogIAogICMgYGF1Z21lbnRgIHdpbGwgc2F2ZSB0aGUgcHJlZGljdGlvbnMgd2l0aCB0aGUgaG9sZG91dCBkYXRhIHNldAogIHJlcyA8LSBhdWdtZW50KG1vZCwgbmV3ZGF0YSA9IGhvbGRvdXQpICU+JQogICAgIyBjYWxjdWxhdGUgcmVzaWR1YWxzIGZvciBmdXR1cmUgdXNlCiAgICBtdXRhdGUoLnJlc2lkID0gbXBnIC0gLmZpdHRlZCkKICAKICAjIFJldHVybiB0aGUgYXNzZXNzbWVudCBkYXRhIHNldCB3aXRoIHRoZSBhZGRpdGlvbmFsIGNvbHVtbnMKICByZXMKfQoKIyBmdW5jdGlvbiB0byByZXR1cm4gTVNFIGZvciBhIHNwZWNpZmljIGhpZ2hlci1vcmRlciBwb2x5bm9taWFsIHRlcm0KcG9seV9tc2UgPC0gZnVuY3Rpb24oaSwgbG9vY3ZfZGF0YSl7CiAgbG9vY3ZfbW9kIDwtIGxvb2N2X2RhdGEgJT4lCiAgICBtdXRhdGUocmVzdWx0cyA9IG1hcChzcGxpdHMsIGhvbGRvdXRfcmVzdWx0cywgaSksCiAgICAgICAgICAgbXNlID0gbWFwX2RibChyZXN1bHRzLCB+IG1lYW4oLiQucmVzaWQgXiAyKSkpCiAgCiAgbWVhbihsb29jdl9tb2QkbXNlKQp9Cgpjdl9tc2UgPC0gZGF0YV9mcmFtZSh0ZXJtcyA9IHNlcShmcm9tID0gMSwgdG8gPSA1KSwKICAgICAgICAgICAgICAgICAgICAgbXNlX2xvb2N2ID0gbWFwX2RibCh0ZXJtcywgcG9seV9tc2UsIGxvb2N2X2RhdGEpKQpjdl9tc2UKCmdncGxvdChjdl9tc2UsIGFlcyh0ZXJtcywgbXNlX2xvb2N2KSkgKwogIGdlb21fbGluZSgpICsKICBsYWJzKHRpdGxlID0gIkNvbXBhcmluZyBxdWFkcmF0aWMgbGluZWFyIG1vZGVscyIsCiAgICAgICBzdWJ0aXRsZSA9ICJVc2luZyBMT09DViIsCiAgICAgICB4ID0gIkhpZ2hlc3Qtb3JkZXIgcG9seW5vbWlhbCIsCiAgICAgICB5ID0gIk1lYW4gU3F1YXJlZCBFcnJvciIpCmBgYAoKQW5kIGFycml2ZSBhdCBhIHNpbWlsYXIgY29uY2x1c2lvbi4gVGhlcmUgbWF5IGJlIGEgdmVyeSBtYXJnaW5hbCBhZHZhbnRhZ2UgdG8gYWRkaW5nIGEgZmlmdGgtb3JkZXIgcG9seW5vbWlhbCwgYnV0IG5vdCBzdWJzdGFudGlhbCBlbm91Z2ggZm9yIHRoZSBhZGRpdGlvbmFsIGNvbXBsZXhpdHkgb3ZlciBhIG1lcmUgc2Vjb25kLW9yZGVyIHBvbHlub21pYWwuCgojIyBMT09DViBpbiBjbGFzc2lmaWNhdGlvbgoKTGV0J3MgdmVyaWZ5IHRoZSBlcnJvciByYXRlIG9mIG91ciBpbnRlcmFjdGl2ZSB0ZXJtcyBtb2RlbCBmb3IgdGhlIFRpdGFuaWMgZGF0YSBzZXQ6CgpgYGB7ciB0aXRhbmljLWxvb2N2fQojIGZ1bmN0aW9uIHRvIGdlbmVyYXRlIGFzc2Vzc21lbnQgc3RhdGlzdGljcyBmb3IgdGl0YW5pYyBtb2RlbApob2xkb3V0X3Jlc3VsdHMgPC0gZnVuY3Rpb24oc3BsaXRzKSB7CiAgIyBGaXQgdGhlIG1vZGVsIHRvIHRoZSBuLTEKICBtb2QgPC0gZ2xtKFN1cnZpdmVkIH4gQWdlICogU2V4LCBkYXRhID0gYW5hbHlzaXMoc3BsaXRzKSwKICAgICAgICAgICAgIGZhbWlseSA9IGJpbm9taWFsKQogIAogICMgU2F2ZSB0aGUgaGVsZG91dCBvYnNlcnZhdGlvbgogIGhvbGRvdXQgPC0gYXNzZXNzbWVudChzcGxpdHMpCiAgCiAgIyBgYXVnbWVudGAgd2lsbCBzYXZlIHRoZSBwcmVkaWN0aW9ucyB3aXRoIHRoZSBob2xkb3V0IGRhdGEgc2V0CiAgcmVzIDwtIGF1Z21lbnQobW9kLCBuZXdkYXRhID0gYXNzZXNzbWVudChzcGxpdHMpKSAlPiUgCiAgICBhc190aWJibGUoKSAlPiUKICAgIG11dGF0ZShwcmVkID0gbG9naXQycHJvYiguZml0dGVkKSwKICAgICAgICAgICBwcmVkID0gYXMubnVtZXJpYyhwcmVkID4gLjUpKQoKICAjIFJldHVybiB0aGUgYXNzZXNzbWVudCBkYXRhIHNldCB3aXRoIHRoZSBhZGRpdGlvbmFsIGNvbHVtbnMKICByZXMKfQoKdGl0YW5pY19sb29jdiA8LSBsb29fY3YodGl0YW5pYykgJT4lCiAgbXV0YXRlKHJlc3VsdHMgPSBtYXAoc3BsaXRzLCBob2xkb3V0X3Jlc3VsdHMpLAogICAgICAgICBlcnJvcl9yYXRlID0gbWFwX2RibChyZXN1bHRzLCB+IG1lYW4oLiRTdXJ2aXZlZCAhPSAuJHByZWQsIG5hLnJtID0gVFJVRSkpKQptZWFuKHRpdGFuaWNfbG9vY3YkZXJyb3JfcmF0ZSwgbmEucm0gPSBUUlVFKQpgYGAKCkluIGEgY2xhc3NpZmljYXRpb24gcHJvYmxlbSwgdGhlIExPT0NWIHRlbGxzIHVzIHRoZSBhdmVyYWdlIGVycm9yIHJhdGUgYmFzZWQgb24gb3VyIHByZWRpY3Rpb25zLiBTbyBoZXJlLCBpdCB0ZWxscyB1cyB0aGF0IHRoZSBpbnRlcmFjdGl2ZSBgQWdlICogU2V4YCBtb2RlbCBoYXMgYSBgciBmb3JtYXRDKG1lYW4odGl0YW5pY19sb29jdiRlcnJvcl9yYXRlLCBuYS5ybSA9IFRSVUUpICogMTAwLCBkaWdpdHMgPSAzKWAlIGVycm9yIHJhdGUuIFRoaXMgaXMgc2ltaWxhciB0byB0aGUgdmFsaWRhdGlvbiBzZXQgcmVzdWx0ICgkYHIgZm9ybWF0QyhtZWFuKHhfdGVzdF9hY2N1cmFjeSRTdXJ2aXZlZCAhPSB4X3Rlc3RfYWNjdXJhY3kkcHJlZCwgbmEucm0gPSBUUlVFKSAqIDEwMCwgZGlnaXRzID0gMylgXCUkKQoKIyMgRXhlcmNpc2U6IExPT0NWIGluIGxpbmVhciByZWdyZXNzaW9uCgoxLiBFc3RpbWF0ZSB0aGUgTE9PQ1YgTVNFIG9mIGEgbGluZWFyIHJlZ3Jlc3Npb24gb2YgdGhlIHJlbGF0aW9uc2hpcCBiZXR3ZWVuIGFkbWlzc2lvbiByYXRlIGFuZCBjb3N0IGluIHRoZSBbYHNjb3JlY2FyZGAgZGF0YXNldF0oc3RhdDAwMl9saW5lYXJfbW9kZWxzLmh0bWwjZXhlcmNpc2U6X2xpbmVhcl9yZWdyZXNzaW9uX3dpdGhfc2NvcmVjYXJkKS4KCiAgICA8ZGV0YWlscz4gCiAgICAgIDxzdW1tYXJ5PkNsaWNrIGZvciB0aGUgc29sdXRpb248L3N1bW1hcnk+CiAgICAgIDxwPgoKICAgIGBgYHtyIHNjb3JlY2FyZC1tc2V9CiAgICBsaWJyYXJ5KHJjZnNzKQogICAgCiAgICAjIGZ1bmN0aW9uIHRvIGVzdGltYXRlIGhlbGRvdXQgcmVzdWx0cyBmb3IgbW9kZWwKICAgIGhvbGRvdXRfcmVzdWx0cyA8LSBmdW5jdGlvbihzcGxpdHMpIHsKICAgICAgIyBGaXQgdGhlIG1vZGVsIHRvIHRoZSBuLTEKICAgICAgbW9kIDwtIGdsbShjb3N0IH4gYWRtcmF0ZSwgZGF0YSA9IGFuYWx5c2lzKHNwbGl0cykpCiAgICAgIAogICAgICAjIFNhdmUgdGhlIGhlbGRvdXQgb2JzZXJ2YXRpb24KICAgICAgaG9sZG91dCA8LSBhc3Nlc3NtZW50KHNwbGl0cykKICAgICAgCiAgICAgICMgYGF1Z21lbnRgIHdpbGwgc2F2ZSB0aGUgcHJlZGljdGlvbnMgd2l0aCB0aGUgaG9sZG91dCBkYXRhIHNldAogICAgICByZXMgPC0gYXVnbWVudChtb2QsIG5ld2RhdGEgPSBob2xkb3V0KSAlPiUKICAgICAgICAjIGNhbGN1bGF0ZSByZXNpZHVhbHMgZm9yIGZ1dHVyZSB1c2UKICAgICAgICBtdXRhdGUoLnJlc2lkID0gY29zdCAtIC5maXR0ZWQpCiAgICAgIAogICAgICAjIFJldHVybiB0aGUgYXNzZXNzbWVudCBkYXRhIHNldCB3aXRoIHRoZSBhZGRpdGlvbmFsIGNvbHVtbnMKICAgICAgcmVzCiAgICB9CiAgICAKICAgIHNjb3JlY2FyZF9sb29jdiA8LSBsb29fY3Yoc2NvcmVjYXJkKSAlPiUKICAgICAgbXV0YXRlKHJlc3VsdHMgPSBtYXAoc3BsaXRzLCBob2xkb3V0X3Jlc3VsdHMpLAogICAgICAgICAgICAgbXNlID0gbWFwX2RibChyZXN1bHRzLCB+IG1lYW4oLiQucmVzaWQgXiAyKSkpCiAgICBtZWFuKHNjb3JlY2FyZF9sb29jdiRtc2UsIG5hLnJtID0gVFJVRSkKICAgIGBgYAogICAgCiAgICAgIDwvcD4KICAgIDwvZGV0YWlscz4KCjEuIEVzdGltYXRlIHRoZSBMT09DViBNU0Ugb2YgYSBbbG9naXN0aWMgcmVncmVzc2lvbiBtb2RlbCBvZiB2b3RlciB0dXJub3V0XShzdGF0MDAzX2xvZ2lzdGljX3JlZ3Jlc3Npb24uaHRtbCNleGVyY2lzZTpfbG9naXN0aWNfcmVncmVzc2lvbl93aXRoX21lbnRhbF9oZWFsdGgpIHVzaW5nIG9ubHkgYG1oZWFsdGhgIGFzIHRoZSBwcmVkaWN0b3IuIENvbXBhcmUgdGhpcyB0byB0aGUgTE9PQ1YgTVNFIG9mIGEgbG9naXN0aWMgcmVncmVzc2lvbiBtb2RlbCB1c2luZyBhbGwgYXZhaWxhYmxlIHByZWRpY3RvcnMuIFdoaWNoIGlzIHRoZSBiZXR0ZXIgbW9kZWw/CgogICAgPGRldGFpbHM+IAogICAgICA8c3VtbWFyeT5DbGljayBmb3IgdGhlIHNvbHV0aW9uPC9zdW1tYXJ5PgogICAgICA8cD4KCiAgICA+IEJlY2F1c2UgdGhpcyBwcm9ibGVtIHJlcXVpcmVzIHR3byBzZXBhcmF0ZSByZWdyZXNzaW9uIGZvcm11bGFzLCByYXRoZXIgdGhhbiB3cml0aW5nIGBob2xkb3V0X3Jlc3VsdHMoKWAgdHdpY2UgSSBjcmVhdGUgYSBzZWNvbmQgYXJndW1lbnQgYGZvcm11bGFgIHRvIHRoZSBmdW5jdGlvbi4gYGFzLmZvcm11bGEoKWAgc3RvcmVzIGEgZm9ybXVsYSBmb3IgYSBmdW5jdGlvbiBhcyBhIHNlcGFyYXRlIG9iamVjdCBhbmQgY2FuIGJlIHBhc3NlZCBkaXJlY3RseSBpbnRvIGBnbG0oKWAuCgogICAgYGBge3IgbWgtbXNlfQogICAgIyBmdW5jdGlvbiB0byBnZW5lcmF0ZSBhc3Nlc3NtZW50IHN0YXRpc3RpY3MgZm9yIHRpdGFuaWMgbW9kZWwKICAgICMgYWRkIHRoZSBmb3JtdWxhIGFyZ3VtZW50IHRvIHBhc3MgdGhlIHJlZ3Jlc3Npb24gZm9ybXVsYQogICAgaG9sZG91dF9yZXN1bHRzIDwtIGZ1bmN0aW9uKHNwbGl0cywgZm9ybXVsYSkgewogICAgICAjIEZpdCB0aGUgbW9kZWwgdG8gdGhlIG4tMQogICAgICBtb2QgPC0gZ2xtKGZvcm11bGEsIGRhdGEgPSBhbmFseXNpcyhzcGxpdHMpLAogICAgICAgICAgICAgICAgIGZhbWlseSA9IGJpbm9taWFsKQogICAgICAKICAgICAgIyBTYXZlIHRoZSBoZWxkb3V0IG9ic2VydmF0aW9uCiAgICAgIGhvbGRvdXQgPC0gYXNzZXNzbWVudChzcGxpdHMpCiAgICAgIAogICAgICAjIGBhdWdtZW50YCB3aWxsIHNhdmUgdGhlIHByZWRpY3Rpb25zIHdpdGggdGhlIGhvbGRvdXQgZGF0YSBzZXQKICAgICAgcmVzIDwtIGF1Z21lbnQobW9kLCBuZXdkYXRhID0gYXNzZXNzbWVudChzcGxpdHMpKSAlPiUgCiAgICAgICAgYXNfdGliYmxlKCkgJT4lCiAgICAgICAgbXV0YXRlKHByZWQgPSBsb2dpdDJwcm9iKC5maXR0ZWQpLAogICAgICAgICAgICAgICBwcmVkID0gYXMubnVtZXJpYyhwcmVkID4gLjUpKQogICAgICAKICAgICAgIyBSZXR1cm4gdGhlIGFzc2Vzc21lbnQgZGF0YSBzZXQgd2l0aCB0aGUgYWRkaXRpb25hbCBjb2x1bW5zCiAgICAgIHJlcwogICAgfQogICAgCiAgICAjIGJhc2ljIG1vZGVsCiAgICBtaF9sb29jdl9saXRlIDwtIGxvb19jdihtZW50YWxfaGVhbHRoKSAlPiUKICAgICAgbXV0YXRlKHJlc3VsdHMgPSBtYXAoc3BsaXRzLCBob2xkb3V0X3Jlc3VsdHMsCiAgICAgICAgICAgICAgICAgICAgICAgICAgIGZvcm11bGEgPSBhcy5mb3JtdWxhKHZvdGU5NiB+IG1oZWFsdGgpKSwKICAgICAgICAgICAgIGVycm9yX3JhdGUgPSBtYXBfZGJsKHJlc3VsdHMsIH4gbWVhbiguJHZvdGU5NiAhPSAuJHByZWQsIG5hLnJtID0gVFJVRSkpKQogICAgbWVhbihtaF9sb29jdl9saXRlJGVycm9yX3JhdGUsIG5hLnJtID0gVFJVRSkKICAgIAogICAgIyBmdWxsIG1vZGVsCiAgICBtaF9sb29jdl9mdWxsIDwtIGxvb19jdihtZW50YWxfaGVhbHRoKSAlPiUKICAgICAgbXV0YXRlKHJlc3VsdHMgPSBtYXAoc3BsaXRzLCBob2xkb3V0X3Jlc3VsdHMsCiAgICAgICAgICAgICAgICAgICAgICAgICAgIGZvcm11bGEgPSBhcy5mb3JtdWxhKHZvdGU5NiB+IC4pKSwKICAgICAgICAgICAgIGVycm9yX3JhdGUgPSBtYXBfZGJsKHJlc3VsdHMsIH4gbWVhbiguJHZvdGU5NiAhPSAuJHByZWQsIG5hLnJtID0gVFJVRSkpKQogICAgbWVhbihtaF9sb29jdl9mdWxsJGVycm9yX3JhdGUsIG5hLnJtID0gVFJVRSkKICAgIGBgYAogICAgCiAgICBUaGUgZnVsbCBtb2RlbCBpcyBiZXR0ZXIgYW5kIGhhcyBhIGxvd2VyIGVycm9yIHJhdGUuCiAgICAKICAgICAgPC9wPgogICAgPC9kZXRhaWxzPgoKIyBrLWZvbGQgY3Jvc3MtdmFsaWRhdGlvbgoKQSBsZXNzIGNvbXB1dGF0aW9uYWxseS1pbnRlbnNpdmUgYXBwcm9hY2ggdG8gY3Jvc3MgdmFsaWRhdGlvbiBpcyAqKiRrJC1mb2xkIGNyb3NzLXZhbGlkYXRpb24qKi4gUmF0aGVyIHRoYW4gZGl2aWRpbmcgdGhlIGRhdGEgaW50byAkbiQgZ3JvdXBzLCBvbmUgZGl2aWRlcyB0aGUgb2JzZXJ2YXRpb25zIGludG8gJGskIGdyb3Vwcywgb3IgKipmb2xkcyoqLCBvZiBhcHByb3hpbWF0ZWx5IGVxdWFsIHNpemUuIFRoZSBmaXJzdCBmb2xkIGlzIHRyZWF0ZWQgYXMgdGhlIHZhbGlkYXRpb24gc2V0LCBhbmQgdGhlIG1vZGVsIGlzIGVzdGltYXRlZCBvbiB0aGUgcmVtYWluaW5nICRrLTEkIGZvbGRzLiBUaGlzIHByb2Nlc3MgaXMgcmVwZWF0ZWQgJGskIHRpbWVzLCB3aXRoIGVhY2ggZm9sZCBzZXJ2aW5nIGFzIHRoZSB2YWxpZGF0aW9uIHNldCBwcmVjaXNlbHkgb25jZS4gVGhlICRrJC1mb2xkIENWIGVzdGltYXRlIGlzIGNhbGN1bGF0ZWQgYnkgYXZlcmFnaW5nIHRoZSBNU0UgdmFsdWVzIGZvciBlYWNoIGZvbGQ6CgokJENWX3soayl9ID0gXGZyYWN7MX17a30gXHN1bV97aSA9IDF9XntrfXtNU0VfaX0kJAoKQXMgeW91IG1heSBoYXZlIG5vdGljZWQsIExPT0NWIGlzIGEgc3BlY2lhbCBjYXNlIG9mICRrJC1mb2xkIGNyb3NzLXZhbGlkYXRpb24gd2hlcmUgJGsgPSBuJC4gTW9yZSB0eXBpY2FsbHkgcmVzZWFyY2hlcnMgd2lsbCB1c2UgJGs9NSQgb3IgJGs9MTAkIGRlcGVuZGluZyBvbiB0aGUgc2l6ZSBvZiB0aGUgZGF0YSBzZXQgYW5kIHRoZSBjb21wbGV4aXR5IG9mIHRoZSBzdGF0aXN0aWNhbCBtb2RlbC4KCiMjIGstZm9sZCBDViBpbiBsaW5lYXIgcmVncmVzc2lvbgoKTGV0J3MgZ28gYmFjayB0byB0aGUgYEF1dG9gIGRhdGEgc2V0LiBJbnN0ZWFkIG9mIExPT0NWLCBsZXQncyB1c2UgMTAtZm9sZCBDViB0byBjb21wYXJlIHRoZSBkaWZmZXJlbnQgcG9seW5vbWlhbCBtb2RlbHMuCgpgYGB7ciAxMF9mb2xkX2F1dG99CiMgbW9kaWZpZWQgZnVuY3Rpb24gdG8gZXN0aW1hdGUgbW9kZWwgd2l0aCB2YXJ5aW5nIGhpZ2hlc3Qgb3JkZXIgcG9seW5vbWlhbApob2xkb3V0X3Jlc3VsdHMgPC0gZnVuY3Rpb24oc3BsaXRzLCBpKSB7CiAgIyBGaXQgdGhlIG1vZGVsIHRvIHRoZSB0cmFpbmluZyBzZXQKICBtb2QgPC0gZ2xtKG1wZyB+IHBvbHkoaG9yc2Vwb3dlciwgaSksIGRhdGEgPSBhbmFseXNpcyhzcGxpdHMpKQogIAogICMgU2F2ZSB0aGUgaGVsZG91dCBvYnNlcnZhdGlvbnMKICBob2xkb3V0IDwtIGFzc2Vzc21lbnQoc3BsaXRzKQogIAogICMgYGF1Z21lbnRgIHdpbGwgc2F2ZSB0aGUgcHJlZGljdGlvbnMgd2l0aCB0aGUgaG9sZG91dCBkYXRhIHNldAogIHJlcyA8LSBhdWdtZW50KG1vZCwgbmV3ZGF0YSA9IGhvbGRvdXQpICU+JQogICAgIyBjYWxjdWxhdGUgcmVzaWR1YWxzIGZvciBmdXR1cmUgdXNlCiAgICBtdXRhdGUoLnJlc2lkID0gbXBnIC0gLmZpdHRlZCkKICAKICAjIFJldHVybiB0aGUgYXNzZXNzbWVudCBkYXRhIHNldCB3aXRoIHRoZSBhZGRpdGlvbmFsIGNvbHVtbnMKICByZXMKfQoKIyBmdW5jdGlvbiB0byByZXR1cm4gTVNFIGZvciBhIHNwZWNpZmljIGhpZ2hlci1vcmRlciBwb2x5bm9taWFsIHRlcm0KcG9seV9tc2UgPC0gZnVuY3Rpb24oaSwgdmZvbGRfZGF0YSl7CiAgdmZvbGRfbW9kIDwtIHZmb2xkX2RhdGEgJT4lCiAgICBtdXRhdGUocmVzdWx0cyA9IG1hcChzcGxpdHMsIGhvbGRvdXRfcmVzdWx0cywgaSksCiAgICAgICAgICAgbXNlID0gbWFwX2RibChyZXN1bHRzLCB+IG1lYW4oLiQucmVzaWQgXiAyKSkpCiAgCiAgbWVhbih2Zm9sZF9tb2QkbXNlKQp9CgojIHNwbGl0IEF1dG8gaW50byAxMCBmb2xkcwphdXRvX2N2MTAgPC0gdmZvbGRfY3YoZGF0YSA9IEF1dG8sIHYgPSAxMCkKCmN2X21zZSA8LSBkYXRhX2ZyYW1lKHRlcm1zID0gc2VxKGZyb20gPSAxLCB0byA9IDUpLAogICAgICAgICAgICAgICAgICAgICBtc2VfdmZvbGQgPSBtYXBfZGJsKHRlcm1zLCBwb2x5X21zZSwgYXV0b19jdjEwKSkKY3ZfbXNlCmBgYAoKSG93IGRvIHRoZXNlIHJlc3VsdHMgY29tcGFyZSB0byB0aGUgTE9PQ1YgdmFsdWVzPwoKYGBge3IgMTBfZm9sZF9hdXRvX2xvb2N2LCBkZXBlbmRzb249YygiMTBfZm9sZF9hdXRvIiwibG9vY3ZfcG9seSIpfQphdXRvX2xvb2N2IDwtIGxvb19jdihBdXRvKQoKZGF0YV9mcmFtZSh0ZXJtcyA9IHNlcShmcm9tID0gMSwgdG8gPSA1KSwKICAgICAgICAgICBgMTAtZm9sZGAgPSBtYXBfZGJsKHRlcm1zLCBwb2x5X21zZSwgYXV0b19jdjEwKSwKICAgICAgICAgICBMT09DViA9IG1hcF9kYmwodGVybXMsIHBvbHlfbXNlLCBhdXRvX2xvb2N2KQopICU+JQogIGdhdGhlcihtZXRob2QsIE1TRSwgLXRlcm1zKSAlPiUKICBnZ3Bsb3QoYWVzKHRlcm1zLCBNU0UsIGNvbG9yID0gbWV0aG9kKSkgKwogIGdlb21fbGluZSgpICsKICBsYWJzKHRpdGxlID0gIk1TRSBlc3RpbWF0ZXMiLAogICAgICAgeCA9ICJEZWdyZWUgb2YgUG9seW5vbWlhbCIsCiAgICAgICB5ID0gIk1lYW4gU3F1YXJlZCBFcnJvciIsCiAgICAgICBjb2xvciA9ICJDViBNZXRob2QiKQpgYGAKClByZXR0eSBtdWNoIHRoZSBzYW1lIHJlc3VsdHMuCgojIyBDb21wdXRhdGlvbmFsIHNwZWVkIG9mIExPT0NWIHZzLiAkayQtZm9sZCBDVgoKIyMjIExPT0NWCgpgYGB7ciBsb29jdl90aW1lfQpsaWJyYXJ5KHByb2Z2aXMpCgpwcm9mdmlzKHsKICBkYXRhX2ZyYW1lKHRlcm1zID0gc2VxKGZyb20gPSAxLCB0byA9IDUpLAogICAgICAgICAgICAgbXNlX3Zmb2xkID0gbWFwX2RibCh0ZXJtcywgcG9seV9tc2UsIGF1dG9fbG9vY3YpKQp9KQpgYGAKCiMjIyAxMC1mb2xkIENWCgpgYGB7ciBrZm9sZF90aW1lfQpwcm9mdmlzKHsKICBkYXRhX2ZyYW1lKHRlcm1zID0gc2VxKGZyb20gPSAxLCB0byA9IDUpLAogICAgICAgICAgICAgbXNlX3Zmb2xkID0gbWFwX2RibCh0ZXJtcywgcG9seV9tc2UsIGF1dG9fY3YxMCkpCn0pCmBgYAoKT24gbXkgbWFjaGluZSwgMTAtZm9sZCBDViB3YXMgYWJvdXQgNDAgdGltZXMgZmFzdGVyIHRoYW4gTE9PQ1YuIEFnYWluLCBlc3RpbWF0aW5nICRrPTEwJCBtb2RlbHMgaXMgZ29pbmcgdG8gYmUgbXVjaCBlYXNpZXIgdGhhbiBlc3RpbWF0aW5nICRrPWByIG5yb3coQXV0bylgJCBtb2RlbHMuCgojIyBrLWZvbGQgQ1YgaW4gbG9naXN0aWMgcmVncmVzc2lvbgoKWW91J3ZlIGdvdHRlbiB0aGUgaWRlYSBieSBub3csIGJ1dCBsZXQncyBkbyBpdCBvbmUgbW9yZSB0aW1lIG9uIG91ciBpbnRlcmFjdGl2ZSBUaXRhbmljIG1vZGVsLgoKYGBge3IgdGl0YW5pY19rZm9sZH0KIyBmdW5jdGlvbiB0byBnZW5lcmF0ZSBhc3Nlc3NtZW50IHN0YXRpc3RpY3MgZm9yIHRpdGFuaWMgbW9kZWwKaG9sZG91dF9yZXN1bHRzIDwtIGZ1bmN0aW9uKHNwbGl0cykgewogICMgRml0IHRoZSBtb2RlbCB0byB0aGUgdHJhaW5pbmcgc2V0CiAgbW9kIDwtIGdsbShTdXJ2aXZlZCB+IEFnZSAqIFNleCwgZGF0YSA9IGFuYWx5c2lzKHNwbGl0cyksCiAgICAgICAgICAgICBmYW1pbHkgPSBiaW5vbWlhbCkKICAKICAjIFNhdmUgdGhlIGhlbGRvdXQgb2JzZXJ2YXRpb25zCiAgaG9sZG91dCA8LSBhc3Nlc3NtZW50KHNwbGl0cykKICAKICAjIGBhdWdtZW50YCB3aWxsIHNhdmUgdGhlIHByZWRpY3Rpb25zIHdpdGggdGhlIGhvbGRvdXQgZGF0YSBzZXQKICByZXMgPC0gYXVnbWVudChtb2QsIG5ld2RhdGEgPSBhc3Nlc3NtZW50KHNwbGl0cykpICU+JSAKICAgIGFzX3RpYmJsZSgpICU+JQogICAgbXV0YXRlKHByZWQgPSBsb2dpdDJwcm9iKC5maXR0ZWQpLAogICAgICAgICAgIHByZWQgPSBhcy5udW1lcmljKHByZWQgPiAuNSkpCgogICMgUmV0dXJuIHRoZSBhc3Nlc3NtZW50IGRhdGEgc2V0IHdpdGggdGhlIGFkZGl0aW9uYWwgY29sdW1ucwogIHJlcwp9Cgp0aXRhbmljX2N2MTAgPC0gdmZvbGRfY3YoZGF0YSA9IHRpdGFuaWMsIHYgPSAxMCkgJT4lCiAgbXV0YXRlKHJlc3VsdHMgPSBtYXAoc3BsaXRzLCBob2xkb3V0X3Jlc3VsdHMpLAogICAgICAgICBlcnJvcl9yYXRlID0gbWFwX2RibChyZXN1bHRzLCB+IG1lYW4oLiRTdXJ2aXZlZCAhPSAuJHByZWQsIG5hLnJtID0gVFJVRSkpKQptZWFuKHRpdGFuaWNfY3YxMCRlcnJvcl9yYXRlLCBuYS5ybSA9IFRSVUUpCmBgYAoKTm90IGEgbGFyZ2UgZGlmZmVyZW5jZSBmcm9tIHRoZSBMT09DViBhcHByb2FjaCwgYnV0IGl0IHRha2UgbXVjaCBsZXNzIHRpbWUgdG8gY29tcHV0ZS4KCiMjIEV4ZXJjaXNlOiBrLWZvbGQgQ1YKCjEuIEVzdGltYXRlIHRoZSAxMC1mb2xkIENWIE1TRSBvZiBhIGxpbmVhciByZWdyZXNzaW9uIG9mIHRoZSByZWxhdGlvbnNoaXAgYmV0d2VlbiBhZG1pc3Npb24gcmF0ZSBhbmQgY29zdCBpbiB0aGUgW2BzY29yZWNhcmRgIGRhdGFzZXRdKHN0YXQwMDJfbGluZWFyX21vZGVscy5odG1sI2V4ZXJjaXNlOl9saW5lYXJfcmVncmVzc2lvbl93aXRoX3Njb3JlY2FyZCkuCgogICAgPGRldGFpbHM+IAogICAgICA8c3VtbWFyeT5DbGljayBmb3IgdGhlIHNvbHV0aW9uPC9zdW1tYXJ5PgogICAgICA8cD4KCiAgICBgYGB7ciBzY29yZWNhcmQtY3Z9CiAgICAjIGZ1bmN0aW9uIHRvIGVzdGltYXRlIGhlbGRvdXQgcmVzdWx0cyBmb3IgbW9kZWwKICAgIGhvbGRvdXRfcmVzdWx0cyA8LSBmdW5jdGlvbihzcGxpdHMpIHsKICAgICAgIyBGaXQgdGhlIG1vZGVsIHRvIHRoZSB0cmFpbmluZyBzZXQKICAgICAgbW9kIDwtIGdsbShjb3N0IH4gYWRtcmF0ZSwgZGF0YSA9IGFuYWx5c2lzKHNwbGl0cykpCiAgICAgIAogICAgICAjIFNhdmUgdGhlIGhlbGRvdXQgb2JzZXJ2YXRpb25zCiAgICAgIGhvbGRvdXQgPC0gYXNzZXNzbWVudChzcGxpdHMpCiAgICAgIAogICAgICAjIGBhdWdtZW50YCB3aWxsIHNhdmUgdGhlIHByZWRpY3Rpb25zIHdpdGggdGhlIGhvbGRvdXQgZGF0YSBzZXQKICAgICAgcmVzIDwtIGF1Z21lbnQobW9kLCBuZXdkYXRhID0gaG9sZG91dCkgJT4lCiAgICAgICAgIyBjYWxjdWxhdGUgcmVzaWR1YWxzIGZvciBmdXR1cmUgdXNlCiAgICAgICAgbXV0YXRlKC5yZXNpZCA9IGNvc3QgLSAuZml0dGVkKQogICAgICAKICAgICAgIyBSZXR1cm4gdGhlIGFzc2Vzc21lbnQgZGF0YSBzZXQgd2l0aCB0aGUgYWRkaXRpb25hbCBjb2x1bW5zCiAgICAgIHJlcwogICAgfQogICAgCiAgICBzY29yZWNhcmRfY3YxMCA8LSB2Zm9sZF9jdihkYXRhID0gc2NvcmVjYXJkLCB2ID0gMTApICU+JQogICAgICBtdXRhdGUocmVzdWx0cyA9IG1hcChzcGxpdHMsIGhvbGRvdXRfcmVzdWx0cyksCiAgICAgICAgICAgICBtc2UgPSBtYXBfZGJsKHJlc3VsdHMsIH4gbWVhbiguJC5yZXNpZCBeIDIpKSkKICAgIG1lYW4oc2NvcmVjYXJkX2N2MTAkbXNlLCBuYS5ybSA9IFRSVUUpCiAgICBgYGAKICAgIAogICAgICA8L3A+CiAgICA8L2RldGFpbHM+CgoxLiBFc3RpbWF0ZSB0aGUgMTAtZm9sZCBDViBNU0Ugb2YgYSBbbG9naXN0aWMgcmVncmVzc2lvbiBtb2RlbCBvZiB2b3RlciB0dXJub3V0XShzdGF0MDAzX2xvZ2lzdGljX3JlZ3Jlc3Npb24uaHRtbCNleGVyY2lzZTpfbG9naXN0aWNfcmVncmVzc2lvbl93aXRoX21lbnRhbF9oZWFsdGgpIHVzaW5nIG9ubHkgYG1oZWFsdGhgIGFzIHRoZSBwcmVkaWN0b3IuIENvbXBhcmUgdGhpcyB0byB0aGUgTE9PQ1YgTVNFIG9mIGEgbG9naXN0aWMgcmVncmVzc2lvbiBtb2RlbCB1c2luZyBhbGwgYXZhaWxhYmxlIHByZWRpY3RvcnMuIFdoaWNoIGlzIHRoZSBiZXR0ZXIgbW9kZWw/CgogICAgPGRldGFpbHM+IAogICAgICA8c3VtbWFyeT5DbGljayBmb3IgdGhlIHNvbHV0aW9uPC9zdW1tYXJ5PgogICAgICA8cD4KCiAgICBgYGB7ciBtaC1jdn0KICAgICMgZnVuY3Rpb24gdG8gZ2VuZXJhdGUgYXNzZXNzbWVudCBzdGF0aXN0aWNzIGZvciB0aXRhbmljIG1vZGVsCiAgICAjIGFkZCB0aGUgZm9ybXVsYSBhcmd1bWVudCB0byBwYXNzIHRoZSByZWdyZXNzaW9uIGZvcm11bGEKICAgIGhvbGRvdXRfcmVzdWx0cyA8LSBmdW5jdGlvbihzcGxpdHMsIGZvcm11bGEpIHsKICAgICAgIyBGaXQgdGhlIG1vZGVsIHRvIHRoZSB0cmFpbmluZyBzZXQKICAgICAgbW9kIDwtIGdsbShmb3JtdWxhLCBkYXRhID0gYW5hbHlzaXMoc3BsaXRzKSwKICAgICAgICAgICAgICAgICBmYW1pbHkgPSBiaW5vbWlhbCkKICAgICAgCiAgICAgICMgU2F2ZSB0aGUgaGVsZG91dCBvYnNlcnZhdGlvbnMKICAgICAgaG9sZG91dCA8LSBhc3Nlc3NtZW50KHNwbGl0cykKICAgICAgCiAgICAgICMgYGF1Z21lbnRgIHdpbGwgc2F2ZSB0aGUgcHJlZGljdGlvbnMgd2l0aCB0aGUgaG9sZG91dCBkYXRhIHNldAogICAgICByZXMgPC0gYXVnbWVudChtb2QsIG5ld2RhdGEgPSBhc3Nlc3NtZW50KHNwbGl0cykpICU+JSAKICAgICAgICBhc190aWJibGUoKSAlPiUKICAgICAgICBtdXRhdGUocHJlZCA9IGxvZ2l0MnByb2IoLmZpdHRlZCksCiAgICAgICAgICAgICAgIHByZWQgPSBhcy5udW1lcmljKHByZWQgPiAuNSkpCiAgICAgIAogICAgICAjIFJldHVybiB0aGUgYXNzZXNzbWVudCBkYXRhIHNldCB3aXRoIHRoZSBhZGRpdGlvbmFsIGNvbHVtbnMKICAgICAgcmVzCiAgICB9CiAgICAKICAgICMgYmFzaWMgbW9kZWwKICAgIG1oX2N2MTBfbGl0ZSA8LSB2Zm9sZF9jdihkYXRhID0gbWVudGFsX2hlYWx0aCwgdiA9IDEwKSAlPiUKICAgICAgbXV0YXRlKHJlc3VsdHMgPSBtYXAoc3BsaXRzLCBob2xkb3V0X3Jlc3VsdHMsCiAgICAgICAgICAgICAgICAgICAgICAgICAgIGZvcm11bGEgPSBhcy5mb3JtdWxhKHZvdGU5NiB+IG1oZWFsdGgpKSwKICAgICAgICAgICAgIGVycm9yX3JhdGUgPSBtYXBfZGJsKHJlc3VsdHMsIH4gbWVhbiguJHZvdGU5NiAhPSAuJHByZWQsIG5hLnJtID0gVFJVRSkpKQogICAgbWVhbihtaF9jdjEwX2xpdGUkZXJyb3JfcmF0ZSwgbmEucm0gPSBUUlVFKQogICAgCiAgICAjIGZ1bGwgbW9kZWwKICAgIG1oX2N2MTBfZnVsbCA8LSB2Zm9sZF9jdihkYXRhID0gbWVudGFsX2hlYWx0aCwgdiA9IDEwKSAlPiUKICAgICAgbXV0YXRlKHJlc3VsdHMgPSBtYXAoc3BsaXRzLCBob2xkb3V0X3Jlc3VsdHMsCiAgICAgICAgICAgICAgICAgICAgICAgICAgIGZvcm11bGEgPSBhcy5mb3JtdWxhKHZvdGU5NiB+IC4pKSwKICAgICAgICAgICAgIGVycm9yX3JhdGUgPSBtYXBfZGJsKHJlc3VsdHMsIH4gbWVhbiguJHZvdGU5NiAhPSAuJHByZWQsIG5hLnJtID0gVFJVRSkpKQogICAgbWVhbihtaF9jdjEwX2Z1bGwkZXJyb3JfcmF0ZSwgbmEucm0gPSBUUlVFKQogICAgYGBgCiAgICAKICAgICAgPC9wPgogICAgPC9kZXRhaWxzPgoKIyBTZXNzaW9uIEluZm8gey50b2MtaWdub3JlfQoKYGBge3IgY2hpbGQ9J19zZXNzaW9uaW5mby5SbWQnfQpgYGAK

This work is licensed under the CC BY-NC 4.0 Creative Commons License.